实施二分查找的缺陷是什么？
二元search比看起来更难实现。 “虽然二分查找的基本思想比较简单，但细节可能会非常棘手……” – Donald Knuth。
哪些错误最有可能被引入新的二进制search实现？
这里有一些我能想到的：
- 当确定下一个时间间隔的边界时， 逐个错误
- 处理重复的项目 ，如果你想返回数组中的第一个相等的项目，而是返回一个后续的平等项目
- 计算索引时数值下溢/溢出 ，数组庞大
- recursion与非recursion实现，您应该考虑的deviseselect
这些是你想到的吗？
这个问题刚刚被问到 。 除了Knuth的说法外，“虽然二分查找的基本思想比较简单，但细节可能会非常棘手”，但是有惊人的历史事实（见TAOCP，第3卷，第6.2.1节），二分查找首先发表在1946年，但第一次发布没有错误的二进制search是在1962年。而且有宾利的经验，当他分配在贝尔实验室和IBM的专业程序员的课程二进制search，并给了他们两个小时，每个人都说他们是对的，并且在检查他们的代码时，他们中的90％有错误 – 年复一年。
也许这么多程序员为什么会在二进制search中犯错误的根本原因是，他们不够小心： 编程珍珠引用这句话 ：“编写你的代码，把它扔在墙上，并有质量保证或testing交易与bug“的方法。 而且有很多的错误的范围。 不只是这里提到的其他几个答案的溢出错误，而是逻辑错误。
以下是一些二进制search错误的例子。 这绝不是详尽无遗的。 （正如托尔斯泰在安娜·卡列尼娜 （ Anna Karenina）所写的：“所有幸福的家庭都是相似的，每个不幸的家庭都以自己的方式不高兴” – 每一个不正确的二进制search程序都是不正确的。
Pattis的
下面的Pascal代码是从Richard E Pattis的二进制search （1988）中的文本Textbook错误中获得的 。 他看了20本教科书，想出了这个二进制search（顺便说一句，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; 看起来好吗？ 这有多个错误。 在进一步阅读之前，看看你是否可以find他们。 即使您第一次看到Pascal，您也应该能够猜到代码的作用。
他描述了许多程序有五个错误，特别是上面的错误：
错误1 ：它不在O（log n）时间运行，其中n =大小。 在对正确编程实践的热情中，一些程序员将二进制search作为函数/过程编写，并将其传递给一个数组。 （这不是Pascal所特有的;设想在C ++中通过值传递一个向量，而不是通过引用传递）。这只是将数组传递给过程的时间（Θ（n）），这会损害整个目的。 更糟糕的是，有些作者显然会给出一个recursion的二进制search，每次都传递一个数组，给出的运行时间是Θ（n log n）。 （这不是很牵强;实际上我看过这样的代码。）
错误2 ：大小= 0时失败。这可能是好的。 但是，根据预期的应用程序，正在search的列表/表可能缩小到0，并且必须在某处处理。
错误3 ：它给出了错误的答案。 只要循环的最后一个循环以Low = High开始（例如当Size = 1时），即使Key在数组中，它也会设置Found：= False。
错误4 ：只要Key小于数组的最小元素，就会导致错误。 （ Index变为1后，将High设置为0等等，导致出界错误。）
错误5 ：只要Key大于数组的最大元素，就会导致错误。 （在Index变成Size ，它将Low设置为Size + 1等;导致出界错误。）
他还指出，一些明显的“修复”这些错误的方法也是错误的。 实际的代码也经常有这个属性，当一个程序员写了一些不正确的东西，发现一个错误，然后“修复”它，直到看起来正确，没有仔细思考。
在他尝试的20本教科书中，只有5本是正确的二进制search。 在剩余的15个（他讽刺地说16）中，他发现了11个错误1，6个错误2，错误3和错误4，以及错误5中的一个。这些数字总共大于15，因为其中有几个有多个错误。
更多的例子
二进制search不仅仅用于search一个数组，以查看它是否包含一个值，所以这里还有一个例子。 我想更多地更新这个列表。
假设你有一个递增（非递减）的函数f：R-> R，并且（因为你想要一个f的根，比方说），你想find最大的t使得f(t) < 0 。 看看你能在下面find多less错误：
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，那么这是错误的，从不比较浮点数是否相等等等）
如何编写二进制search
我曾经犯过几个这样的错误 – 前几十次我写二进制search（这是在编程比赛时间压力），大约30％的时间有一个错误的地方 – 直到我find简单的方法来写它正确。 我没有二进制search错误，因为（我记得）。 诀窍很简单：
保持不变。
find/决定，并明确一些不变的属性，你的“低”和“高”variables满足整个循环：之前，期间和之后。 确保它从来没有违反。 当然你也需要考虑终止条件。 编程珍珠的第四章详细解释了这个问题，它从半forms方法派生出一个二分查找程序。
例如，要稍微抽象出正在检查的条件，假设您想要find某个条件位置poss(x)为真的最大整数值x 。 即使这个问题定义的明确性比很多程序员开始的还要多。 （例如，对于某个值v ， poss(x)可能是a[x] ≤ v ;这是为了找出sorting后的数组a有多less元素比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);
你可以添加更多的assert语句和其他检查，但基本的想法是因为只有当你知道poss(mid)是真的时才更新lo ，所以你保持poss(lo)始终为真的不variables。 同样，只有当poss(mid)为false时，你才会将hi设置为mid ，所以你保持poss(hi)始终为false的不variables。 分别考虑终止条件。 （请注意，当hi-lo为1时， mid与lo相同，因此不要将while循环写为while(hi>lo) ，否则会产生无限循环。）循环结束时，我保证hi-lo最多是1，而且因为你始终保持你的不变（ poss(lo)是真的， poss(hi)是false），所以它不能是0.另外，因为你的不variables， lo是返回/打印/使用的值。 还有其他的方法来编写二进制search当然，但保持不变是一个技巧/纪律总是有帮助的。
阅读这个 。 Java的二进制search实现隐藏了近十年的错误，然后才有人发现它。
该错误是整数溢出。 它不会导致人们的问题，因为几乎没有人search足够大的数据结构。
如果你在附近有编程珍珠书，你应该检查第4章。
编辑2：正如评论中指出的那样，你可以下载我提到的作者网站的草案章节： http : //www.cs.bell-labs.com/cm/cs/pearls/sketch04.html
没有考虑到在计算两个指数之间的中点时，总和高和低的值可能导致整数溢出。
参考
人们无法正确执行二进制search的一个重要原因是我们没有很好地表征二进制search，这是一个明确定义的问题，但通常没有很好的定义。
一个普遍的规则是从失败中学习。 在这里，思考“无效”的案例有助于澄清问题。 如果input是空的呢？ 如果input包含重复项呢？ 我应该通过一个条件testing还是两个testing（加上一个额外的testing提前终止）每个迭代？ 和其他技术问题，如计算指数中的数值上溢/下溢等技巧。
@ Zach Scrivena指出，通过对问题进行特征化可以避免的错误是错误的处理和处理重复的项目。
许多人认为二进制search是给定sorting数组的目标值。 这就是如何使用二进制，而不是二进制search本身。
我将尝试给出一个相对严格的二进制search的定义/expression方式，并通过符合一种特定的方法来显示脱离一个错误和重复问题的一种方式，当然这不是一个新的方法。
# (my) definition of binary search: input: L: a 'partially sorted' array, key: a function, take item in L as argument prerequisite: by 'partially sorted' I mean, if apply key function to all item of L, we get a new array of bool, L_1, such that it can't be partitioned to two left, right blocks, with all item in left being false, all item in right being true. (left or/and right could be empty) output: the index of first item in right block of L_1 (as defined in prerequisite). or equivalently, the index of first item in L such that key(item) == True
这个定义自然解决了重复的问题。
通常有两种方法来表示数组，[]和[），我更喜欢后者，[]方法的等价性是使用（start，count）对来代替。
# Algorithm: binary search # input: L: a 'partially sorted' array, key: a function, take item in L as argument while L is not empty: mid = left + (right - left)/2 # or mid = left + count/2 if key(mid item) is True: recede right # if True, recede right else: forward left # if False, forward left return left
因此，如果你把你的“如果真，退货（结束）”和“如果假，前进（开始）”部分权利，你几乎完成。 我把它称为二进制search的“FFTR规则”。 如果要find第一个项目，就像在上面的定义中一样，左边是开始，但是如果你要find最后一个项目，那么右边就会开始。 我符合[]时尚，那么一个可能的实现是，
while left<right: mid = left + (right - left)/2 if key(L(mid)) == True: right = mid else: left = mid+1 return left
让我们进一步validation它，首先显示收敛，然后显示正确性。
收敛：
whenever left == right, we exit loop (also true if being empty at the first) so, in the loop, if denote, diff = (right - left)/2, lfstep = 1 + diff/2, 'lfstep' for 'left index forward step size' rbstep = diff - diff/2, 'rbstep' for 'right index back (recede) step size' it can be show that lfstep and rbstep are alway positive, so left and right will be equal at last. both lfstep and rbstep are asymptotically half of current subarray size, so it's of logarithm time complexity.
正确性：
if the input array is empty: return the left index; else: if key(mid item) is true: "recede right" so mid and all item after mid are all true, we can reduce the search range to [left, mid), to validate it, there are two possible cases, case 1: mid is the first item such that key(item) is True, so there are no true items in new search range [left, mid), so the test will always be false, and we forward left at each iteration until search range is empty, that is [finalleft,mid), since we return finalleft, and finalleft == mid, correctly done! case 2: there are item before mid such that key(item) is True, in this case we just reduce to a new problem of smaller size else: "forward left" mid and all item before mid is false, since we are to find the first true one, we can safely reduce to new search range [mid+1, right) without change the result.
等价（开始，计数）版本，
while count>0: mid = start + count/2 if key(L[mid]) == True: right = mid else: left = mid+1 return left
总结一下 ，如果符合[]惯例，
1. define your key function of your problem, 2. implement your binary search with "FFTR rule" -- "recede (end) if True ( key(item) == True) else forward (start)" examples: if to find a value target, return index or -1 if not found, key = lambda x: x>=target, if L[found_index] == target: return found_index else: return -1
至于提前终止一个额外的testing，我不认为这值得付出，但你可以尝试。
现代处理器的stream水线体系结构比进行具有大量决策和分支的二进制search更适合于进行线性search。
因此，当一个简单的线性search更快，当然更简单的时候，一个常见的性能问题和一个过早的优化 （你知道，这些是所有邪恶的根源）是使用二分search。
根据读取次数的不同，即使对数据进行sorting也会使事情变得更慢。 线性和二进制之间的盈亏平衡点对于简单的键（例如32位整数）可以容易地在1000个元素处。
