c++ - 要在 vector 中找到中间项，为什么要使用 "mid = beg + (end - beg)/2"而不是 "mid = (beg + end)/2"

我是C++的新手。我在网上看到了这段代码，试图在 vector 中找到一个字符串。但是，我已经注意到即将结束:

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;
        }
        mid = beg + (end - beg) / 2;
    }

最佳答案

通常，对于二进制搜索，其原因是为了避免溢出。 beg+end可能会因为较大的值而溢出。使用end-beg可以避免溢出。

想象beg是MAX_INT-3而end是MAX_INT-1，那么beg+end会大于MAX_INT，但是end-beg只会是2。

对于迭代器，这也是可行的，因为end-begin是数字，而begin+end无效。您可以减去两个迭代器以获取它们之间的距离，但不能添加两个迭代器。

关于c++ - 要在 vector 中找到中间项，为什么要使用 "mid = beg + (end - beg)/2"而不是 "mid = (beg + end)/2"，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35422254/