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

7 回答

• 58

  以下是我能想到的一些内容：

  • Off-by-one errors ，确定下一个区间的边界时

  • Handling of duplicate items ，如果你想要返回数组中的第一个相等的项目，而是返回一个后续的相等项目

  • Numerical underflows/overflows 计算索引时，使用大型数组

  • Recursive vs non-recursive 实施，你应该考虑的设计选择

  这些是你的想法吗？

  回复于 2024-04-27T23:16:55+08:00
• 1

  这个问题是just asked again recently . 除了Knuth的引用"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky"之外，还有令人震惊的历史事实（参见TAOCP，第3卷，第6.2.1节），二元搜索首次发布于1946年，但第一次发布的没有错误的二进制搜索是在1962年 . 并且有Bentley的经验当他在贝尔实验室和IBM这样的地方为专业程序员分配二进制搜索并给他们两个小时时，每个人都报告他们说得对，并且在检查他们的代码时，90％的人都有年复一年的错误 .

  也许除了斯特金定律之外，这么多程序员在二元搜索中犯错误的根本原因在于他们不够谨慎：编程珍珠引用这个作为"write your code, throw it over the wall, and have Quality Assurance or Testing deal with the bugs"方法 . 并且存在很多错误的余地 . 不仅仅是这里提到的其他几个答案的溢出错误，而是逻辑错误 .

  以下是二进制搜索错误的一些示例 . 这绝不是详尽无遗的 . （正如托尔斯泰在安娜卡列尼娜写的那样 - "All happy families are alike; every unhappy family is unhappy in its own way" - 每个不正确的二进制搜索程序都以其自己的方式不正确 . ）

  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;
  

  看起来不错？这有多个错误 . 在进一步阅读之前，看看你是否能找到它们 . 即使您第一次看到Pascal，您也应该能够猜出代码的作用 .

  ---

  他描述了许多程序所具有的五个错误，特别是上面的错误：

  Error 1 ：它不在O（log n）时间内运行，其中n = Size . 在他们对Proper Programming Practice的热情中，一些程序员将二进制搜索作为函数/过程编写，并将其传递给数组 . （这不是特定于Pascal;想象一下，在C中通过值而不是通过引用传递矢量 . ）这是Θ（n）时间，只是为了将数组传递给过程，这会破坏整个目的 . 更糟糕的是，一些作者显然给出了递归二进制搜索，每次都传递一个数组，给出的运行时间为Θ（n log n） . （这不是牵强附会;我实际上看过这样的代码 . ）

  Error 2 ：当size = 0时失败 . 这可能没问题 . 但是根据预期的应用程序，被搜索的列表/表可能缩小为0，并且必须在某处处理 .

  Error 3 ：答案错误 . 每当循环的最后一次迭代以Low = High开始时（例如当Size = 1时），即使 Key 在数组中，它也会设置Found：= False .

  Error 4 ：只要 Key 小于数组的最小元素，就会导致错误 . （在 Index 变为1之后，它将 High 设置为0，等等;导致越界错误 . ）

  Error 5 ：只要 Key 大于数组的最大元素，就会导致错误 . （在 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％的时间存在错误 - 直到我找到了编写它的简单方法正确 . （因为我记得），我没有错误的二进制搜索 . 诀窍很简单：

  保持不变 .

  查找/决定并明确你的"low"和"high"变量在整个循环中满足的一些不变属性：之前，期间和之后 . 确保它永远不会被侵犯 . 当然，您还需要考虑终止条件 . 这在Pearls编程的第4章中有详细解释，它从半形式方法中导出二进制搜索程序 .

  例如，要稍微抽象出被检查的条件，假设您要查找某个条件 poss(x) 为真的最大整数值 x . 即使是问题定义的这种明确性也不仅仅是许多程序员的开端 . （例如，对于某些值 v ， poss(x) 可能是 a[x] ≤ 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);
  

  您可以添加更多断言语句和其他检查，但基本思路是因为只有在知道 poss(mid) 为真时才将 lo 更新为 mid ，所以保持 poss(lo) 始终为真的不变量 . 同样，仅当 poss(mid) 为false时才将 hi 设置为 mid ，因此您保持 poss(hi) 始终为false的不变量 . 分别考虑终止条件 . （注意，当 hi-lo 为1时， mid 与 lo 相同 . 所以不要将循环写为 while(hi>lo) ，否则'll have a infinite loop.) At the end of the loop, you'保证 hi-lo 最多为1，因为你总是保持你的不变量（ poss(lo) 为真且 poss(hi) 是的，它不能为0.而且，再次因为你的不变量，你知道 lo 是返回/打印/使用的值 . 当然还有其他方法来编写二进制搜索，但保持不变是一个技巧/总是有帮助的纪律 .

  回复于 2024-04-27T23:16:55+08:00
• 29

  Read this . Java的二进制搜索实现在任何人发现它之前隐藏了差不多十年的错误 .

  这个bug是整数溢出 . 它没有引起人们的问题，因为几乎没有人在搜索足够大的数据结构 .

  回复于 2024-04-27T23:16:55+08:00
• -1

  如果你附近有编程珍珠书，你应该查看第4章 .

  edit2：正如评论中指出的那样，你可以下载我提到作者网站的章节草稿：http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html

  回复于 2024-04-27T23:16:55+08:00
• 2

  人们无法正确实现二进制搜索的一个重要原因是我们 don't characterize binary search well, it is a well-defined problem but usually one doesn't define it well.

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

  正如@Zach Scrivena指出的那样，通过表征问题可以避免的错误是一个一个错误，以及处理重复的项目 .

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

  I'll try to give a relative rigorous definition/formulation of binary search, and show one way to get off off-by-one error and duplicate issues, 符合一种具体的方法，当然不是新方法 .

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

  因此，如果你使你的 "if True, Recede (end)" 和 "if False, Forward (start) " 部分正确，你就差不多完成了 . 我称之为 the "FFTR rule" of binary search. 如果要找到第一个项目，如上面的定义，左边将是开始，但是如果你要找到最后一个项目，则将开始正确 . 我遵循[）时尚，然后是一个可能的工具是，

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

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

  convergence:

  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.
  

  correctness:

  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
  

  to summarize ，如果符合[）惯例，

  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
  

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

  回复于 2024-04-27T23:16:55+08:00
• 14

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

  Reference

  回复于 2024-04-27T23:16:55+08:00
• 7

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

  因此，当简单的线性搜索更快且当然更简单时，常见的 performance bug 和 premature optimization （你知道，这些是所有邪恶的根源）正在使用二进制搜索 .

  根据读取次数的不同，即使对数据进行排序也会使事情变得更慢 . 对于简单的键（例如32位整数），线性和二进制之间的收支 balancer 点可以很容易地为1000个元素 .

  回复于 2024-04-27T23:16:55+08:00