相关疑难解决方法(0)

我正在阅读一本算法书,其中包含以下二进制搜索算法:

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 …

我是C++的新手.我在网上看到了这个代码,它试图在向量中找到一个字符串.但是,我注意到了最后:

mid = beg + (end - beg) / 2;

为什么必须以这种方式编写,为什么不能写成:

mid = (beg + end) /2

是mid = (beg + (end - 1)) / 2可行的替代方案吗？

我很难理解它背后的原因.

vector<string> text = {"apple", "beer", "cat", "dog"};
    string sought = "beer";

    auto beg = text.begin(), end = text.end();
    auto mid = text.begin() + (end - beg) / 2;
    while (mid != end && *mid != sought){
        if(sought < *mid){
            end = mid;
        } else {
            beg = mid + 1;
        } …