二分查找算法与随机二分查找算法的时间复杂度研究(3)
2 算法简介及时间复杂度分析
2．1 经典二分查找算法
将一个给定的元素x与一个已排序数组A[low…high]的中间元素做比较，如果x < A[mid]，这里mid = floor((low+high)/2)，则不考虑A[mid…high]，而是对A[low…mid-1]重复实施相同的方法。类似地，如果x > A[mid]，则放弃A[low…mid]，并对A[mid+1…high] 重复实施相同的方法。如此，我们就可以使用递归方法来实现这一搜索算法（伪代码如下）：
输入：n个元素的升序数组A[1…n]和元素x
输出：若x=A[j], 1£j£n, 则输出j, 否则输出0
low←1; high ←n; j←0
while(low £high) and (j=0)
mid ← ë( low+high)/2û
if x=A[mid] then j ←mid
else if x<A[mid] then high ←mid-1
else low ←mid+1
end while
return j
对于上面的经典二分查找的伪代码，我们作简要分析：为了求出算法的执行时间，我们计算元素间的比较次数，因为这是一个基本运算，也就是说，算法的执行时间与完成元素间比较次数是成比例的。我们将假定每个if-else-else比较当作一次比较来计算，首先注意到当n=0时，即数组是空的，则算法不执行任何元素的比较。当n=1时，else的部分将被执行，并且若x≠A[mid]，算法将对空数组递归。从而得到当n=1时，算法刚好执行一次比较。如果n>1，则存在两种可能；当x=A[mid]时，则算法仅仅执行一次比较；否则算法所需的比较次数是1加上由递归调用数组的前或后一半所执行的比较次数。如果设C(n)表示算法对大小为n的数组在最坏的情况下所执行的比较次数，则C(n)可表示为如下的递推式：
1 若n=1
1+C( ) 若n≥2
设对某个整数k≥2,满足2 ≤n≤2 。展开上述递推式，可得到