61

二进制搜索比看起来更难实现。“虽然二分搜索的基本思想相对简单，但细节却出奇地棘手……”——唐纳德·克努斯。

哪些错误最有可能被引入到新的二分搜索实现中？

4

7 回答 7

74

这个问题最近又被问到了。除了 Knuth 的名言“虽然二分搜索的基本思想比较简单，但细节可能出奇地棘手”，还有一个惊人的历史事实（参见 TAOCP，第 3 卷，第 6.2.1 节），二分搜索首次发表于1946 年，但第一次发布没有错误的二进制搜索是在 1962 年。Bentley 的经验是，当他在贝尔实验室和 IBM 等地的专业程序员课程中分配二进制搜索并给他们两个小时时，每个人都报告说他们做对了，在检查他们的代码时，90% 的人年复一年地有错误。

除了鲟鱼定律之外，这么多程序员在使用二分搜索时出错的根本原因可能是他们不够小心：Programming Pearls将其引用为“编写代码，将其扔到墙上，然后获得质量保证或测试协议”与错误”的方法。并且有很大的错误空间。不仅仅是这里的其他几个答案提到的溢出错误，还有逻辑错误。

下面是一些二进制搜索错误的示例。这绝不是详尽无遗的。（正如托尔斯泰在《安娜·卡列尼娜》中所写——“所有幸福的家庭都是相似的；每个不幸的家庭都各有各的不幸”——每一个不正确的二分搜索程序都有其不正确的一面。）

帕蒂斯

以下 Pascal 代码取自 Richard E Pattis 的论文Textbook errors in binary search (1988)。他看了二十本教科书，想到了这个二分搜索（顺便说一句，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，您也应该能够猜到代码的作用。

他描述了许多程序存在的五个错误，尤其是上述错误：

错误 1：它不在 O(log n) 时间内运行，其中 n = 大小。出于对正确编程实践的热情，一些程序员将二进制搜索编写为一个函数/过程，并将其传递给一个数组。（这不是 Pascal 特有的；想象在 C++ 中通过值而不是通过引用传递向量。）这只是将数组传递给过程的 Θ(n) 时间，这违背了整个目的。更糟糕的是，一些作者显然给出了递归二进制搜索，每次都传递一个数组，运行时间为 Θ(n log n)。（这并不牵强；我实际上见过这样的代码。）

错误 2：当 size = 0 时失败。这可能没问题。但是根据预期的应用程序，正在搜索的列表/表可能会缩小到 0，并且必须在某个地方进行处理。

错误3：它给出了错误的答案。每当循环的最终迭代以 Low=High 开始时（例如，当 Size=1 时），它设置 Found:=False，即使Key在数组中也是如此。

错误 4Key ：只要小于数组的最小元素，就会导致错误。（Index变为 1 后设置High为 0 等；导致越界错误。）

错误 5Key ：只要大于数组的最大元素，就会导致错误。（Index变为之后Size，它设置Low为 Size+1 等；导致越界错误。）

他还指出，“修复”这些错误的一些明显方法也被证明是错误的。现实生活中的代码也经常有这个属性，当程序员写了一些不正确的东西，发现了一个错误，然后“修复”它直到它看起来正确而没有仔细考虑。

在他尝试的 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% 的时间在某个地方有一个错误——直到我找到了写它的简单方法正确。从那以后（我记得）我没有错误地进行二分搜索。诀窍很简单：

保持不变。

查找/决定并明确说明您的“低”和“高”变量在整个循环中满足的一些不变属性：之前、期间和之后。确保它永远不会被违反。当然你还需要考虑终止条件。这在Programming Pearls的第 4 章中有详细的解释，它从半形式化方法派生了一个二分搜索程序。

例如，为了稍微抽象出正在检查的条件，假设您想找到x某个条件poss(x)为真的最大整数值。即使是问题定义的这种明确性也超出了许多程序员的起点。（例如，poss(x)可能是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到，所以您保持始终为真的不变量。同样，您设置为仅当为假时，因此您保持始终为假的不变量。单独考虑终止条件。（注意 when为 1，与 相同。所以不要将循环写为，否则会出现无限循环。）在循环结束时，保证最多为 1，因为你总是保持你的不变量（是真的并且mid poss(mid)poss(lo)himidposs(mid)poss(hi)hi-lomidlowhile(hi>lo)hi-loposs(lo)poss(hi)为假），它不能为 0。另外，由于您的不变量，您知道这lo是返回/打印/使用的值。当然，还有其他编写二进制搜索的方法，但维护不变量是一种总是有帮助的技巧/纪律。

于 2011-06-18T01:49:15.377 回答
35

以下是我能想到的一些：

  • 在确定下一个区间的边界时出现逐一错误
  • 重复项的处理，如果您想返回数组中的第一个相等项，而是返回一个后续相等项
  • 计算索引时的数值下溢/溢出，具有巨大的数组
  • 递归与非递归实现，您应该考虑的设计选择

这些是你心目中的吗？

于 2009-02-02T18:38:29.590 回答
16

读这个。Java 的二进制搜索实现在任何人发现它之前隐藏了将近十年的错误。

该错误是整数溢出。它没有引起人们的问题，因为几乎没有人在搜索足够大的数据结构。

于 2009-02-02T18:41:02.330 回答
4

人们无法正确实现二分搜索的一个关键原因是我们没有很好地描述二分搜索，这是一个定义明确的问题，但通常没有很好地定义它。

一个普遍的规则是从失败中学习。在这里，考虑“无效”案例有助于澄清问题。如果输入为空怎么办？如果输入包含重复项怎么办？每次迭代我应该通过一个条件测试还是两个测试（加上提前终止的额外测试）来实现它？以及其他技术问题，例如计算索引中的数值溢出/下溢，以及其他技巧。

正如@Zach Scrivena 指出的那样，可以通过很好地描述问题来避免的错误是一个错误和重复项目的处理。

许多人将二进制搜索视为在给定排序数组的情况下找到目标值。这就是二进制的使用方式，而不是二进制搜索本身。

我将尝试给出二进制搜索的相对严格的定义/公式，并展示一种通过遵循一种特定方法来解决一个错误和重复问题的方法，这当然不是新的。

# (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

因此，如果您将“如果为真，则后退（结束）”和“如果为假，则向前（开始）”部分正确，您几乎完成了。我称之为二分搜索的“FFTR 规则”。如果要找到第一个项目，如上面的定义，左边将是开始，但是如果你要找到最后一个项目，右边将是开始。如果你符合 [) 时尚，那么一个可能的实现是，

while left<right:
    mid = left + (right - left)/2
    if key(L(mid)) == True:
        right = mid
    else:
        left = mid+1
    return left

让我们进一步验证它，首先显示收敛，然后显示正确性。

收敛：

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

至于通过额外的测试提前终止，我认为不值得，但你可以试试。

于 2016-04-23T06:14:38.913 回答
1

在计算两个索引之间的中点时，如果不考虑将高值和低值相加，可能会导致整数溢出。

参考

于 2009-02-02T18:41:23.547 回答
0

现代处理器的流水线架构更适合进行线性搜索，而不是进行具有大量决策和分支的二进制搜索。

因此，一个常见的性能错误和过早的优化（你知道，这些是万恶之源）是使用二进制搜索，而简单的线性搜索会更快，当然更简单。

根据读取的数量，即使对数据进行排序也会使事情变慢。对于简单的键（例如 32 位整数），线性和二进制之间的收支平衡点很容易达到 1000 个元素。

于 2012-02-24T19:18:08.360 回答
0

我在实现二分搜索时遇到的一个错误是在计算中间元素时整数范围溢出。众所周知，二分查找实现的步骤是：

  1. 找到中间元素。
  2. 检查是否：
  • 目标元素大于中间元素，从中间+1搜索到结束索引
  • 目标元素小于中间元素，从start到mid-1索引搜索
  • 目标元素等于中间元素，返回索引。

在上述所有步骤中，都会重新计算中间元素。现在，中间元素被发现为： mid = (start+end)/2 现在，如果结束索引太高（对于非常大的数组），它可能会溢出 INT 范围。所以，一个更好的方法是：mid = start + (end-start)/2

如果您仔细检查，最终它会给我们相同的值，但我们摆脱了可能遇到的溢出问题。

此外，正如我们所知，二进制搜索只能在排序列表上实现。假设在问题中说明输入列表已排序，但未提及它是按升序还是降序排列。在这种情况下，您可能需要添加一个额外的条件来检查它。

于 2021-09-06T06:43:20.823 回答