Двоичный поиск с использованием итераторов, почему мы используем «(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; 

Пожалуйста, помогите.

Answer 1

Бинарный поиск традиционно написан так. Эта форма написания помогает кодировщикам понимать двоичный поиск, поскольку в стандартном бинарном поиске используется только начало, конец, середина.

Вы могли использовать size() вместо end-starперед циклом, но вы должны использовать end-start в то время как петли, так как end-start изменится. Вы должны избегать использования size() для обеспечения согласованности.

Answer 2

Это делается для того, чтобы избежать переполнения, которое может произойти при добавлении двух очень больших целых чисел, где результат сложения может превышать максимальный предел максимального значения и дает странные результаты.

Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

Из блога:

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;