使用迭代器进行二进制搜索，为什么我们使用“（end-begin）/ 2”？ [英] Binary search using iterators, why do we use "(end - begin)/2"?

问题描述

我正在研究迭代器，并且已经停留3天了解我们为什么要使用：

I am studying iterators and have been stuck for 3 days on figuring out why do we use:

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;

请帮忙。

推荐答案

这样做是为了避免在添加两个非常大的整数时可能发生的溢出，其中加法结果可能变得大于最大整数限制并产生奇怪的结果。

This is done to avoid overflow that may happen in adding two very big integers where the addition result may become greater than the max integer limit and yield weird results.

额外，额外 - 阅读全部内容：几乎所有二进制搜索和合并都被破坏

来自博客：

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;

这篇关于使用迭代器进行二进制搜索，为什么我们使用“（end-begin）/ 2”？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！