Unterschied zwischen der grundlegenden binären Suche nach Ober- und Untergrenze?

Question

In dem Artikel http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch diskutiert der Autor binäre Suche. Er unterscheidet zwischen dem Finden des niedrigsten Wertes, wo etwas wahr ist, und dem höchsten Wert, wo etwas falsch ist. Das Array sieht durchsucht so etwas wie:

false false false true true

Ich bin neugierig, warum diese beiden Fälle unterschiedlich sind. Warum kannst du nicht einfach den niedrigsten Wert finden, der wahr ist, dann subtrahierst du eins, um den höchsten Wert zu finden, der falsch ist?

Edit2: Ok, also verstehe ich untere gegen obere Grenze. Nun, ich habe Mühe zu verstehen, wenn wir nach der kleinsten Ganzzahl größer oder gleich der Abfrage suchen, warum können wir nicht einfach die if(mid>query) zu if(mid>=query) ändern und es tun, anstatt Obergrenze zu tun.

Edit: Hier ist, was der Artikel heißt es:

„Jetzt endlich kommen wir zu dem Code, der wie in diesem und dem vorhergehenden Abschnitt beschrieben binäre Suche implementiert:

binary_search(lo, hi, p): 
    while lo < hi: 
     mid = lo + (hi-lo)/2 
     if p(mid) == true: 
     hi = mid 
     else: 
     lo = mid+1 

    if p(lo) == false: 
     complain    // p(x) is false for all x in S! 

    return lo   // lo is the least x for which p(x) is true 

...

Wenn wir das letzte x finden wollten, für das p (x) falsch ist, würden wir (unter Verwendung eines ähnlichen Grundprinzips wie oben) etwas wie:

binary_search(lo, hi, p): 
    while lo < hi: 
     mid = lo + (hi-lo+1)/2 // note: division truncates 
     if p(mid) == true: 
     hi = mid-1 
     else: 
     lo = mid 

    if p(lo) == true: 
     complain    // p(x) is true for all x in S! 

    return lo   // lo is the greatest x for which p(x) is false 

. "

Answer 1

Die untere und obere Grenze einer binären Suche sind die niedrigste und die höchste Position, an der der Wert eingefügt werden kann, ohne die Reihenfolge zu unterbrechen. (In der C++ Standard-Bibliothek, werden diese Grenzen durch Iteratoren dargestellt werden Referenzierung des Elements vor dem der Wert eingesetzt werden könnte, aber das Konzept ist nicht wesentlich verändert.)

Nehmen wir zum Beispiel ein sortierter Bereich

1 2 3 4 5 5 5 6 7 9 

in einer binären Suche nach 3, werden wir

v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
    ^-- upper bound 

Und in einer binären Suche haben für 5:

 v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
      ^-- upper bound 

Die untere und obere Grenze sind identisch, wenn das Element nicht im Bereich existiert.In einer binären Suche nach 8:

    v-- lower bound 
1 2 3 4 5 5 5 6 7 9 
       ^-- upper bound 

Der Autor des Artikels, zu dem Sie Sätze all dies in die entsprechenden Begriffe von „kleiner als“ und beziehen sich „größer als“, so dass bei einer Suche von 5,

 v-- lower bound 
t t t t f f f f f f  <-- smaller than? 
1 2 3 4 5 5 5 6 7 9 
f f f f f f f t t t  <-- greater than? 
      ^-- upper bound 

Die C++ - Iteratoren beziehen sich in allen diesen Fällen auf das Element direkt hinter der Grenze. Das heißt:

• Auf der Suche nach 3, der Iterator von std::lower_bound zurück 3 beziehen würde und die ein std::upper_bound-4
• Auf der Suche nach 5, dem Iterator von std::lower_bound zurück beziehen würde würde beziehen sich auf die erste 5 und derjenige von std::upper_bound für 8-6
• auf der Suche beziehen würde, würden beide auf 9 beziehen

Dies liegt daran, dass die Konvention in der C++ - Standardbibliothek für Einfügungen einen Iterator enthält, der sich auf das Element bezieht, vor dem das neue Element eingefügt werden soll. Zum Beispiel, nach

std::vector<int> vec { 1, 3, 4, 5, 5, 5, 6, 7, 9 }; 
vec.insert(vec.begin() + 1, 2); 

vec enthalten würde 1, 2, 3, 4, 5, 5, 5, 6, 7, 9. std::lower_bound und std::upper_bound folgen dieser Konvention so dass

vec.insert(std::lower_bound(vec.begin(), vec.end(), 5), 5); 
vec.insert(std::upper_bound(vec.begin(), vec.end(), 8), 8); 

Arbeit wie gewünscht und vec sortiert verlassen.

Allgemeiner ist dies ein Ausdruck der Art, wie Bereiche in der C++ - Standardbibliothek angegeben sind. Der Anfangsiterator eines Bereichs bezieht sich auf das erste Element des Bereichs (falls vorhanden), während der Enditerator auf das Element (falls vorhanden) direkt hinter dem Ende des Bereichs verweist. Eine andere Möglichkeit, dies zu betrachten, ist, dass die von std::lower_bound und std::upper_bound zurückgegebenen Iteratoren den Bereich der Elemente im gesuchten Bereich umfassen, die dem gesuchten Element entsprechen.

Dieser Bereich ist leer, wenn das Element nicht in dem Bereich liegt, so dass lower_bound und upper_bound die gleiche Iterator zurück und sonst lower_bound gibt einen Iterator auf das erste Element in dem gesuchten Bereich bezieht, die während upper_bound auf den Suchwert äquivalent sind Gibt einen Iterator zurück, der auf das Element (falls vorhanden) verweist, das direkt hinter dem letzten solchen Element liegt.

Answer 2

Wenn das Array immer

false … true … 

Dann wird der Index vor dem sein wird Sie immer falsch sein finden, wenn Sie bei index 0 wahr finden. Ein anderer Grenzfall, wie in meinem Kommentar oben erwähnt, ist, wenn Sie true nicht finden. Dann ist der höchste falsche Teil der letzte Teil des Arrays.

Answer 3

Die beiden Algorithmen unterscheiden sich offensichtlich in den Zustand, was passieren soll, wenn es keine true oder kein false Wert als eigentlich ganz offensichtlich aus dem Code-Snippet ist: Wenn Sie den niedrigsten Wert finden, wo der Wert true und subtrahieren 1 Von dieser Position aus wird das Ergebnis false mit dem höchsten Wert gefunden, und ein falsches Ergebnis wird erzeugt, da es kein solches Objekt gibt. Da die Algorithmen einfach auf verschiedene Elemente abzielen, die sich mit der direkten Lokalisierung des entsprechenden Elements befassen, anstatt einen speziellen Fall zu haben, wird auch vermieden, dass ein spezieller Fall behandelt werden muss, wodurch die Menge an Code reduziert wird. Da Spezialfallcode für jeden Algorithmusaufruf nur einmal ausgeführt wird, ist es wahrscheinlich, dass er etwas schlechter abläuft als der Sonderfall. Dies ist etwas, das es wert ist, gemessen zu werden.

Beachten Sie, dass das Codebeispiel nicht C++ ist, obwohl die Frage C++ markiert ist. Als Ergebnis ist es kein idiomatisches C++. Der typische Ansatz in C++, etwas wie lower_bound() oder upper_bound() zu implementieren, besteht darin, geeignete Iteratoren zu verwenden. Diese Algorithmen würden sich nicht "beschweren", wenn es kein geeignetes Element gibt, da sie einfach einen Iterator an der geeigneten Position erzeugen würden, d. H. Einen Iterator für den Start für std::lower_bound() und einen Iterator für die Vergangenheit an dem Ende für std::upper_bound().