Der Unterschied zwischen basic binären Suche für die Obere Grenze und untere Grenze?

In dem Artikel http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarysearch-Methode, bespricht die Autorin die binäre Suche. Er macht einen Unterschied zwischen der Suche nach dem niedrigsten Wert, wo etwas wahr ist, und der höchste Wert, wo etwas falsch ist.
Das array durchsucht werden, sieht etwas aus wie:

false false false true true

Ich bin neugierig, warum diese beiden Fälle sind unterschiedlich. Warum können Sie nicht einfach finden, die niedrigsten Wert, welcher true ist, dann subtrahieren eines zu finden, der höchste Wert, der falsch ist?

Edit2: Ok, also verstehe ich das untere vs. Obere Schranke. Nun, ich habe Schwierigkeiten zu verstehen, bei der Suche für die kleinste Ganzzahl, die größer oder gleich der Abfrage, warum können wir nicht einfach ändern if(mid>query) zu if(mid>=query) haben und es tun untere statt Obere Schranke.

Edit: Hier ist was in dem Artikel hieß es:

"Jetzt bekommen wir endlich den code implementiert die binäre Suche wie beschrieben in diesem und dem vorherigen Abschnitt:

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 wollten, um die letzten x, für die p(x) ist falsch, wir würden ausdenken (mit einer ähnlichen Begründung wie oben), so 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

."

Gut, im vorausgesetzt, dass die binäre Suche impliziert der Satz in etwa so aussieht wie falsch .... false true ... true egal, was
Der Artikel im bezieht, impliziert, dass dies der Fall ist, wenn wir uns binäre Suche; ich glaube, das ist auch eine Notwendigkeit für die binäre Suche, um auch auf die situation.
sicher, aber konnte Sie leicht überprüfen, mit wie if(lo==0&&works(lo)==true)return false?

InformationsquelleAutor John Targaryen | 2015-02-08

  1. 31

    Den unteren und oberen Grenze einer binären Suche werden die höchste und die niedrigste position, wo der Wert eingefügt werden könnte, ohne die Bestellung. (In der C++ - standard-Bibliothek, diese Schranken werden vertreten durch Iteratoren verweisen auf das element, bevor der Wert eingefügt werden könnte, aber das Konzept ist nicht wesentlich verändert.)

    Nehmen, zum Beispiel, eine sortierte Auswahl

    1 2 3 4 5 5 5 6 7 9

    In eine binäre Suche für 3 wir haben

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

    Und in eine binäre Suche für 5:

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

    Die untere und Obere Schranke gleich sind, wenn das element nicht vorhanden in der Auswahl. In eine binäre Suche für 8:

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

    Den Autor des Artikels, auf den Sie sich beziehen-Sätze ist in die äquivalenten Begriffe "kleiner als" und "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

    Den C++ - Iteratoren wird, in all diesen Fällen beziehen sich auf das element direkt hinter der Schranke. Das heißt:

    • Bei der Suche nach 3, der iterator zurückgegeben std::lower_bound finden würde, um 3 und der von std::upper_bound finden würde, um 4
    • Bei der Suche nach 5, der iterator zurückgegeben std::lower_bound würde sich auf den ersten 5 und der von std::upper_bound finden würde, um 6
    • Bei der Suche nach 8, würden beide beziehen sich auf 9

    Dies ist, weil die Konvention in den C++ - standard-Bibliothek für Insertionen ist die übergabe eines iterator bezogen auf das element, 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 lassen vec sortiert.

    Mehr im Allgemeinen, dies ist ein Ausdruck der Art und Weise Bereiche angegeben werden, die im C++ standard-Bibliothek. Der Anfang iterator für einen Bereich bezieht sich auf das erste element des Bereichs (wenn überhaupt), während der Ende-iterator bezieht sich auf das element (falls vorhanden) direkt hinter das Ende der Reihe. Ein weiterer Weg, um es zu betrachten ist, dass die Iteratoren zurückgegeben std::lower_bound und std::upper_bound span die Anzahl der Elemente im gesuchten Bereich, sind äquivalent zu den gesuchten element.

    Dieser Bereich ist leer, wenn das element nicht in der Auswahl, so dass lower_bound und upper_bound wieder den gleichen iterator und sonst lower_bound gibt einen iterator bezogen auf das erste element der gesuchte Bereich entspricht das der Suche nach Wert, während upper_bound gibt einen iterator bezogen auf das element (falls vorhanden), die direkt hinter der letzten ein solches element.

    Ah, ich hatte nicht bedacht, der Fall, wo mehrere Werte sind die gleichen wie die Abfrage. Allerdings, in deinem Dritten Beispiel, wenn das element nicht existiert, ist nicht Obere Schranke 9 und Untergrenze 7?
    Im C++ - standard-Bibliothek Begriffe, die Iteratoren erhalten Sie von lower_bound und upper_bound würde sowohl in Referenz 9 denn bevor dieses element ist sowohl die höchste und die niedrigste Stelle, wo eine 8 eingefügt werden könnte. Der Ort, wo das element wirklich konnte nicht eingefügt werden, wird immer einer der Lücken oder enden, aber.
    lower_bound und upper_bound handeln in übereinstimmung mit der Allgemeinen iterator-Konventionen in der stdlib es -- es ist das gleiche für vector::insert, wo die Weitergabe vec.begin() + 1 wird es fügen Sie das neue element vor dem aktuellen zweiten element, und in anderen, ähnlichen zusammenhängen. Dies ist, so dass Sie weitergeben können, das Ergebnis lower_bound und upper_bound direkt auf diese Funktionen und haben Sie das richtige tun.
    ist das erste element, das nicht weniger als 8, und upper_bound ist das erste element, das mehr als 8. In beiden Fällen, das ist die 9.

    InformationsquelleAutor Wintermute

  2. 1

    Wenn das array wird immer

    false … true …

    Dann den index, bevor die, die Sie finden, wird immer falsch sein, es sei denn, Sie finden true index 0. Eine weitere Grenze Falle, wie bereits in meinem Kommentar oben, ist, wenn Sie nicht finden true. Dann, die höchsten false wird der Letzte Teil der Reihe.

    Konnten Sie nicht aufpassen, beide mit einfachen booleschen wenn Prüfungen? Zum Beispiel if(array[0]==true||array[array.size]==false)return false? Auch, wie würde die änderung im code, der dieses problem beheben?
    Das ist sozusagen der Punkt. Wenn x ist der index für true, x-1 ist nicht zwingend die Grenze für die false. Sie müssen sagen if x > 0 && !array[x-1] (zweiter Teil optional).

    InformationsquelleAutor royhowie

  3. 0

    Werden die beiden algorithmen offensichtlich unterscheiden sich in der Bedingung von dem, was geschehen sollte, wenn gibt es keine true oder keine false Wert so wie er ist eigentlich ziemlich offensichtlich aus dem code-snippet: wenn Sie den niedrigsten Wert, wobei der Wert true und subtrahieren Sie 1 von dieser position aus zu finden, der höchste Wert nachgeben false ein Falsches Ergebnis produziert wird, als dort ist kein solches Objekt. Da die algorithmen einfach auf verschiedene Elemente, die den Umgang mit dem Auffinden der entsprechenden Elemente direkt anstatt mit einem speziellen Fall auch vermieden, dass der Umgang mit einem speziellen Fall, die Verringerung der Menge an code. Seit Sonderfall-code neigt dazu, nur einmal ausgeführt werden für jeden Algorithmus-Aufruf es ist voraussichtlich leicht schlechter als die Vermeidung der Besondere Fall. Das ist etwas, was Wert sein kann, Messen.

    Beachten Sie, dass das code-Beispiel ist nicht C++ - trotz der Frage, die tagged-C++. Als ein Ergebnis ist es nicht idiomatischen C++. Der typische Ansatz in C++ zu implementieren, die so etwas wie lower_bound() oder upper_bound() ist, geeignete Iteratoren. Diese algorithmen nicht "beschweren", wenn es kein entsprechendes element als würden Sie produzieren nur einen iterator, der entsprechenden position, d.h., ein iterator auf den Anfang für std::lower_bound() und ein past-the-end-iterator für std::upper_bound().

    Ah, ich tagged it c++ für diesen genauen Grund. Ich war nicht ganz sicher, ob lower_bound sollte Rückkehr kleinste element reibe als Abfrage, oder größte element kleiner als Abfrage. Auch habe ich nicht ganz verstanden, was du meinst mit "Da Sonderfall-code neigt dazu, nur einmal ausgeführt werden für jeden Algorithmus-Aufruf es ist voraussichtlich leicht schlechter als die Vermeidung der Besondere Fall." Wie wäre es um etwas Schlimmeres? Eine einzige if-Anweisung wäre der einzige Unterschied zwischen den beiden, so dass der Unterschied sollte vernachlässigbar sein.

    InformationsquelleAutor Dietmar Kühl

Schreibe einen Kommentar