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

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。”