Binäre Suche mit Iteratoren, warum verwenden wir "(end - begin)/2"?

Question

ich Iteratoren studiere und haben für 3 Tage auf, herauszufinden, warum verwenden wir stecken geblieben:

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

Code:

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"); 
} 

warum tun

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

und nicht:

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

Bitte helfen Sie.

Answer 1

Binäre Suche wird traditionell so geschrieben. Diese Art des Schreibens hilft Programmierern, die binäre Suche zu verstehen, da nur Start, Ende, Mitte in einer Standard-Binärsuche verwendet wird.

Sie könntesize() verwenden, anstatt end-starvor der Schleife, aber Sie haben seit end-start ändern würde end-start in der while-Schleife verwenden. Sie sollten size() aus Konsistenzgründen vermeiden.

Answer 2

Dies wird durchgeführt, um einen Überlauf zu vermeiden, der beim Hinzufügen von zwei sehr großen Ganzzahlen auftreten kann, wobei das Additionsergebnis größer als die maximale Ganzzahl wird und seltsame Ergebnisse liefert.

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

Aus dem Blog:

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;