Im Artikelhttp: //community.topcoder.com/tc? module = Static & d1 = Tutorials & d2 = binarySearch, der Autor diskutiert die binäre Suche. Er unterscheidet zwischen dem niedrigsten Wert, bei dem etwas wahr ist, und dem höchsten Wert, bei dem etwas falsch ist. Das zu durchsuchende Array sieht ungefähr so aus:

false false false true true

Ich bin gespannt, warum diese beiden Fälle unterschiedlich sind. Warum können Sie nicht einfach den niedrigsten Wert finden, der wahr ist, und dann einen subtrahieren, um den höchsten Wert zu finden, der falsch ist?

Edit2: Ok, also ich verstehe untere gegen obere Schranke. Nun habe ich Probleme zu verstehen, warum wir bei der Suche nach der kleinsten Ganzzahl, die größer oder gleich der Abfrage ist, nicht einfach das @ ändern könneif(mid>query) zuif(mid>=query) und lassen Sie es unterer statt oberer Grenze tun.

Bearbeiten: Hier ist, was der Artikel sagte:

"Jetzt kommen wir endlich zu dem Code, der die binäre Suche implementiert, wie in diesem und im vorherigen Abschnitt beschrieben:

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 einer ähnlichen Begründung wie oben) so etwas ausdenken 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

. "