使用迭代器进行二分查找，为什么要使用“(end - begin)/2”？

Question

我正在学习迭代器，已经卡了3天了，一直在思考为什么要使用：

auto mid = text.begin() + (end - beg) / 2;

代码：

int main()

{
    vector<int> text{ 10,9,8,7,6,5,4,3,2,1 };
    int sought = 3;
    // text must be sorted
    // beg and end will denote the range we're searching
    auto beg = text.begin(), end = text.end();
    auto mid = text.begin() + (end - beg) / 2; // original midpoint
                                               // while there are still elements to look at and we haven't yet found sought
    while (mid != end && *mid != sought) {
        if (sought < *mid) // is the element we want in the first half?
            end = mid; // if so, adjust the range to ignore the second half
        else // the element we want is in the second half
            beg = mid + 1; // start looking with the element just after mid
        mid = beg + (end - beg) / 2;// new midpoint
    }

    system("pause");
}

为什么要

auto mid = text.begin() + (end - beg) / 2;

而不是：

auto mid = text.begin() + text.size() / 2;

Please help.

- jibzoiderz

---

我们使用"(end-begin)/2"吗？你在哪里找到这个的？ - Wolf

@Wolf - C++ Primer第五版。这本书在第3.4章中说这是一个“经典算法”，所以我认为这是一个常见的情况（如果我错了，请纠正我）。 - jibzoiderz

这个例子让人困惑的原因是它在主函数中实现了二分查找。如果将其正确地提取到一个只接受迭代器范围进行搜索的函数中，那么为什么不能在容器上调用size就会变得清晰明了——因为你没有办法引用容器。 - Sebastian Redl

实现数学公式时的溢出问题 - phuclv

Answer 1

这样做是为了避免在加两个非常大的整数时可能发生的溢出，导致加法结果超过最大整数限制并产生奇怪的结果。 额外信息-读完所有关于它的内容：几乎所有二进制搜索和归并排序都已经损坏 来自博客：

So what's the best way to fix the bug? Here's one way:
 6:             int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:
 6:             int mid = (low + high) >>> 1;

In C and C++ (where you don't have the >>> operator), you can do this:
 6:             mid = ((unsigned int)low + (unsigned int)high)) >> 1;

- Yavar

---

指针根本不支持加法运算；大整数索引很少会溢出（数组的大小通常远小于整数的极限值）。 - vincent163

我在谈论一种通用技术，而不是特定于指针的。问题表明OP只是想知道为什么不是（beg + end）/ 2？请阅读我的答案中的链接（Google研究博客），以了解更多详细信息。 - Yavar

Answer 2

传统上，二分查找的写法如下。这种写法有助于程序员理解标准二分查找中只使用了起始、结束和中间三个参数。

在循环之前，您可以使用 size() 而不是 end-start，但在 while 循环中必须使用 end-start，因为 end-start 会发生变化。为了保持一致性，应避免使用 size()。

- vincent163

---

所以这更多是形式上的吗？ - jibzoiderz

@jibzoiderz 是的，但是 while 循环中的 end-start 不能被修改。 - vincent163

哦，当beg和end是指针时，你不应该使用beg+end，因为它可能会溢出。 - vincent163

谢谢你的提示！ - jibzoiderz

@HeWenYang ite + n 是可以的，ite1 - ite2 也是可以的，但是 ite1 + ite2 是未定义的。 - chenzhongpu