是否可以在二次搜索算法的每次迭代中只进行一次比较？

Question

在二进制搜索算法中,我们有两个比较:

if (key == a[mid]) then found;

else if (key < a[mid]) then binary_search(a[],left,mid-1);
      else binary_search(a[],mid+1,right);

有没有办法让我只有一个比较而不是上面两个.

-

谢谢

Alok.Kr.

Answer 1

看到:

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

来自维基:

   low = 0
   high = N
   while (low < high) {
       mid = low + ((high - low) / 2)
       if (A[mid] < value)
           low = mid + 1;
       else
            //can't be high = mid-1: here A[mid] >= value,
            //so high can't be < mid if A[mid] == value
            high = mid;
   }
   // high == low, using high or low depends on taste
   if ((low < N) && (A[low] == value))
       return low // found
   else
       return -1 // not found

来自wiki的优点/缺点: "这种方法放弃了在发现匹配时提前终止的可能性,因此成功的搜索具有log2(N)次迭代而不是预期的log2(N)-1次迭代.另一方面,这种实现使得更少的比较:log2(N)小于1.5的两次测试实现(log2(N) - 1)的预期比较次数,N大于8."