c - 二元搜索算法的每次迭代是否可能只有一个比较？

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

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);

有没有一种方法可以让我只有一个比较而不是上面的两个。

--

谢谢

阿罗克

最佳答案

看:

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

摘自Wiki:

   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 )小于N大于8的两次测试实现1·5(log2(N)− 1)的预期比较次数。”

关于c - 二元搜索算法的每次迭代是否可能只有一个比较？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3500167/