这个问题是最近刚刚又问了一遍 https://stackoverflow.com/questions/6372037/binary-search-problems。除了 Knuth 引用的“虽然二分搜索的基本思想相对简单，但细节却出奇的棘手”之外，还有一个令人震惊的历史事实（参见 TAOCP，第 3 卷，第 6.2.1 节）：二分搜索首次发表于1946年却首次发表二分查找没有错误1962 年。Bentley 的经验是，当他在贝尔实验室和 IBM 等地的专业程序员课程中布置二分搜索并给他们两个小时时，每个人都报告说他们做对了，在检查他们的代码时，90% 的人都说他们做对了年复一年地出现错误。
也许除了斯特金定律之外，这么多程序员在二分查找中犯错误的根本原因是他们不够小心：编程珍珠将此引用为“编写代码，将其扔到墙上，然后通过质量保证或测试来处理错误”的方法。而且有很大的出错空间。不仅仅是这里其他几个答案提到的溢出错误，还有逻辑错误。
以下是二分搜索错误的一些示例。这绝不是详尽无遗的。 （正如托尔斯泰在《安娜·卡列尼娜—“幸福的家庭都是相似的；不幸的家庭各有各的不幸”——每一个不正确的二分查找程序都有自己不正确的方式。）
Pattis
以下Pascal代码摘自论文二分查找中的教科书错误(1988) 理查德·E·帕蒂斯。他查看了 20 本教科书，并提出了这个二分搜索（顺便说一句，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;
看起来还好吗？这有不止一个错误。在进一步阅读之前，看看您是否能找到全部。即使您是第一次看到 Pascal，您也应该能够猜出代码的作用。
他描述了许多程序存在的五个错误，特别是上述错误：
Error 1：它不会在 O(log n) 时间内运行，其中 n = Size。出于对正确编程实践的热情，一些程序员将二分搜索编写为函数/过程，并将其传递给一个数组。 （这不是 Pascal 所特有的；想象一下在 C++ 中按值而不是按引用传递向量。）仅将数组传递给过程就需要 θ(n) 时间，这违背了整个目的。更糟糕的是，一些作者显然给出了递归的二分查找，每次传递一个数组，运行时间为 θ(n log n)。 （这并不牵强；我实际上见过这样的代码。）
Error 2：当 size = 0 时失败。这可能没问题。但根据预期的应用程序，正在搜索的列表/表格may缩小到0，必须在某个地方进行处理。
Error 3: 给出了错误的答案。每当循环的最终迭代以 Low=High 开始时（例如，当 Size=1 时），它会设置 Found:=False，即使Key是在数组中。
Error 4: 每当出现错误时Key小于数组的最小元素。 （后Index变为1，则设置High至 0 等；导致越界错误。）
Error 5: 每当出现错误时Key大于数组的最大元素。 （后Index变成Size，它设置Low大小+1等；导致越界错误。）
他还指出，一些“修复”这些错误的明显方法也被证明是错误的。现实生活中的代码也经常具有这种属性，当程序员写了一些不正确的东西，发现错误，然后“修复”它，直到它seemed没有仔细思考就正确。
在他尝试的 20 本教科书中，只有 5 本的二分查找是正确的。在剩下的 15 个中（讽刺的是，他说是 16 个），他发现了 11 个错误 1 实例，6 个错误 2 实例，错误 3 和 4 各两个，以及错误 5 一个。这些数字加起来远远超过 15，因为其中有几个有多个错误。
更多示例
二分搜索不仅仅用于搜索数组以查看它是否包含值，因此现在再举一个例子。当我想到更多时，我可能会更新这个列表。
假设您有一个递增（非递减）函数 f：R->R，并且（例如，因为您想要 f 的根），您想要找到最大的t这样f(t) < 0。看看您能在以下内容中找到多少个错误：
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);
（有些：[0,INF]中可能没有这样的t，如果f在某个区间上为 0 那么这是错误的，切勿比较浮点数是否相等等）
如何编写二分查找
我曾经犯过几个这样的错误 - 最初我编写二分搜索的几十次（这是在时间压力的编程竞赛期间），大约 30% 的时间在某个地方出现错误 - 直到我找到了编写它的简单方法正确。从那以后（我记得）我就没有犯过二分搜索错误。技巧很简单：
保持不变式。
查找/决定并明确您的“低”和“高”变量在整个循环中满足的一些不变属性：之前、期间和之后。确保它永远不会被违反。当然你还需要考虑终止条件。这在第 4 章中有详细解释编程珍珠 which derives半正式方法的二分搜索程序。
例如，为了稍微抽象出正在检查的条件，假设您想找到最大的整数值x对于某些条件poss(x)是真的。甚至这种问题定义的明确性也超出了许多程序员的起点。 （例如，poss(x) may be a[x] ≤ v为了某种价值v;这是为了找出排序数组中有多少元素a大于v，比如说。）然后，编写二分搜索的一种方法是：
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);
您可以添加更多断言语句和其他检查，但基本思想是因为您更新lo to mid only当你知道的时候poss(mid)是真的，你保持不变poss(lo)总是正确的。同样，你设置hi to mid只有当poss(mid)是假的，所以你保持不变式poss(hi)总是假的。单独考虑终止条件。 （请注意，当hi-lo is 1, mid是相同的lo。所以不要将循环写为while(hi>lo)，否则就会出现无限循环。）在循环结束时，可以保证hi-lo至多为 1，并且因为你始终保持不变（poss(lo)是真的并且poss(hi)是假的），它不能是 0。另外，再次由于你的不变量，你知道lo是要返回/打印/使用的值。当然，还有其他方法可以编写二分搜索，但维护不变量是一个总是有帮助的技巧/规则。
