在二进制搜索计算中旬 [英] Calculating mid in binary search

问题描述

我在读一本算法的书，有以下算法二进制搜索：

I was reading an algorithms book which had the following algorithm for binary search:

public class BinSearch {
  static int search ( int [ ] A, int K ) {
    int l = 0 ;
    int u = A. length −1;
    int m;
    while (l <= u ) {
      m = (l+u) /2;
      if (A[m] < K) {
        l = m + 1 ;
      } else if (A[m] == K) {
        return m;
        } else {
          u = m−1;
        }
       }
       return −1;
      }
 }

笔者说：错误是在分配 M =（L + U）/ 2; 它会导致溢出 并应 M = L +（UL）/ 2 所取代。

The author says "The error is in the assignment m = (l+u)/2; it can lead to overflow and should be replaced by m = l + (u-l)/2."

我看不出将导致溢出。当我运行的算法在我脑海中的几个不同的输入，我没有看到中期的价值走出去数组索引。 因此，在这种情况下，将溢出发生的？

I can't see how that would cause an overflow. When I run the algorithm in my mind for a few different inputs, I don't see the mid's value going out of the array index. So, in which cases would the overflow occur?

感谢你。

推荐答案

本的帖子涵盖了很多细节的这个著名的bug。正如其他人说，这是一个溢出问题。推荐链接的解决方法是如下：

This post covers this famous bug in a lot of detail. As others have said it's an overflow issue. The fix recommended on the link is as follows:

int mid = low + ((high - low) / 2);

// Alternatively
int mid = (low + high) >>> 1;

这篇关于在二进制搜索计算中旬的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！