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

Question

我是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;
        }
        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无效.您可以减去两个迭代器以获得它们之间的距离,但是您不能添加两个迭代器.