实现二进制搜索有哪些陷阱？

二进制搜索比它看起来更难实现."尽管二元搜索的基本思想相对简单,但细节却令人惊讶地难以理解......" - 唐纳德克努特.

哪些错误最有可能被引入新的二进制搜索实现？

最近刚刚再次提出这个问题.除了Knuth的引用之外,"尽管二元搜索的基本思想相对简单,但细节可能会非常棘手",有一个令人震惊的历史事实(参见TAOCP,第3卷,第6.2.1节),二元搜索首次发布于1946年,第一次发布没有错误的二进制搜索是在1962年.并且有宾利的经验,当他在贝尔实验室和IBM这样的地方为专业程序员分配二进制搜索并给他们两个小时时,每个人都报告他们说得对,并且在检查他们的代码时,90%的人都有年复一年的错误.

也许除了斯特金定律之外,这么多程序员在二元搜索中犯错误的根本原因在于他们不够谨慎:编程珍珠称这是"编写你的代码,把它扔到墙上,并有质量保证或测试交易与错误"接近.并且存在很多错误的余地.不仅仅是这里提到的其他几个答案的溢出错误,而是逻辑错误.

以下是二进制搜索错误的一些示例.这绝不是详尽无遗的.(正如托尔斯泰在安娜卡列尼娜写的那样- "所有幸福的家庭都是一样的;每个不幸的家庭都以自己的方式不开心" - 每一个不正确的二元搜索程序都以自己的方式不正确.)

Pattis的

以下Pascal代码取自Richard E Pattis的二元搜索(1988)中的Textbook errors.他查看了二十本教科书并提出了这种二分法搜索(BTW,Pascal使用从1开始的数组索引):

PROCEDURE BinarySearch (A         : anArray,
                        Size      : anArraySize,
                        Key       : INTEGER,
                        VAR Found : BOOLEAN;
                        VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN         
   LOW := 1;
   High := Size;

   REPEAT
      Index := (Low + High) DIV 2;
      If Key < A[Index]
         THEN High := Index - 1
         ELSE Low  := Index + 1
   UNTIL (Low > High) OR (Key = A[Index]);

   FOUND := (Low <= High)
END;

float high = INF, low = 0;
while(high != low) {
   float mid = (low + high)/2;
   if(f(mid)>0) high=mid;
   else low=mid;
}
printf("%f", high);

int lo=0, hi=n;
//INVARIANT: poss(lo) is true, poss(hi) is false
//Check and ensure invariant before starting binary search
assert(poss(lo)==true);
assert(poss(hi)==false);
while(hi-lo>1) {
    int mid = lo + (hi-lo)/2;
    if(poss(mid)) lo = mid;
    else hi = mid;
}
printf("%d \n",lo);