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

Question

我是 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;
    }

Answer 1

一般用二分查找，原因是为了避免溢出。 beg+end 容易溢出大值。使用 end-beg 避免溢出。

假设beg是MAX_INT-3，end是MAX_INT-1，那么beg +end 会大于 MAX_INT，但是 end-beg 只会是 2。

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