二分搜索算法利用的算法是（）

A.分治策略

B.动态规划法

C.贪心法

D.回溯法

关于搜索算法的比较，下列说法正确的是_______。

A 通常情况下，哈希算法是计算机中搜索数据的最快方法

B 哈希搜索的运行速度取决于类别中对象的数量和类别的数量

C 采用二分搜索法搜索关键词的速度很快，但如果想要增加一个关键词的话，搜索 速度就会明显变慢

D 如果需要存在插入、删除、修改的情况，一般使用“二叉搜索树”的方法

利用二分查找算法查找序列中的某一个数是否存在，如果序列总共有15个元素，而第一次查找时发现序列中的第8个元素大于要查找的元素，则需要进行的赋值操作是()?

A：low=mid+1

B：low=mid-1

C：high=mid+1

D：high=mid-1

KMP算法通过模式串的前缀函数,较好地利用了搜索过程中的部分匹配信息,从而提高了效率.然而在某些情况下,还可以更好地利用部分匹配信息.例如,考察图9-2中,KMP算法对主串aabaaaab和模式串aaaab的搜索过程.

在图9-2(a)中匹配失败后,按前缀函数指示继续作了图(b)~(d)的比较后,最后在图(e)找到一个匹配.事实上,图(b)~(d)的比较都是多余的.因为模式串在位置0、1、2处的字符和位置3处的字符都相等,因此不需要再和主串中位置3处的字符比较,而可以将模式一次向右滑动4个字符,直接进入图(e)的比较.这就是说,在KMP算法中遇到p[j+1]≠t[i],且p[j+1]=p[next[j]+1]时,可一次向右滑动j-next[next[j]]个字符,而不是j-next[j]个字符.根据此观察,设计一个改进的前缀函数,使得遇到上述特殊情况时效率更高.

如何使用PHP描述顺序查找和二分查找(也叫做折半查找)算法？顺序查找必须考虑效率，对象可以是一个有序数组

在Internet上的搜索引擎经常需要对信息进行比较。例如，可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1，2，…，n的排列i₁，i₂，...，i_n，如果其中存在i_j，i_k，使得j<k但是i_j>i_k，那么就称(i_j，i_k)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如，排列263451含有8个逆序(2，1)，(6，3)，(6，4)，(6，5)，(6，1)，(3，1)，(4，1)，(5，1)，它的逆序数就是8。显然，由1，2，…，n构成的所有n!个排列中，最小的逆序数是0，对应的排列就是12…n;最大的逆序数是n(n-1)/2，对应的排列就是n(n-1)…21。逆序数越大的排列与原始排列的差异度就越大。不难看到，如果使用顺序枚举逆序的蛮力算法来计算排列的逆序数，最坏情况下需要O(n²)的时间。利用二分归并排序算法Mergesort可以设计一个计数逆序的更好的算法，它仅使用O(nlog n)的时间。它的主要思想是：在递归调用算法分别对子数组L₁与L₂排序时，计数每个子数组内部的逆序;在归并排好序的子数组L₁与L₂的过程中，计数L₁的元素与L₂的元素之间产生的逆序。在算法运行中每次得到的逆序数都加到逆序总数上。下面是一个归并过程的例子。

假如两个排好序的子数组是1，4，5和2，3，6，在归并时，先比较1和2，1<2，没有逆序，移走1，第一个数组剩下2个数;接着比较4和2，4>2，第一个数组的4，5都与2构成逆序，即(4，2)，(5，2)，产生的逆序数恰好等于第一个数组剩下的元素个数。移走2，逆序总数加2。接着比较4和3，移走3，再增加2个逆序;接着比较4和6，移走4，不增加逆序;比较5和6，移走5，不增加逆序。在这个过程中逆序数共增加了4，恰好等于1，4，5与序列2，3，6的数之间构成的逆序总数。

(1)根据上面的描述写出算法的伪码。

(2)如果n是2的幂，计算算法使用的比较次数。

使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()

A.O(N)

B.O(logN)

C.O(N*N)

D.O(N*logN)