Mit C ++ erläuterte binäre Suchalgorithmen

Die binäre Suche ist einer dieser Algorithmen, auf die Sie in jedem (guten) Einführungskurs in die Informatik stoßen werden. Es ist ein effizienter Algorithmus zum Finden eines Artikels in einer geordneten Liste. Für dieses Beispiel nehmen wir einfach an, dass dies ein Array ist.

Die Ziele der binären Suche sind:

  • in der Lage sein, die Hälfte des Arrays bei jeder Iteration zu verwerfen
  • Minimieren Sie die Anzahl der Elemente, die wir durchlaufen müssen
  • Hinterlassen Sie uns einen letzten Wert

Nehmen Sie zum Beispiel das folgende Array von ganzen Zahlen:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Angenommen, wir versuchen, den Indexwert der Zahl 7 in diesem Array zu ermitteln. Insgesamt gibt es 17 Elemente und die Indexwerte reichen von 0 bis 16.

Wir können sehen, dass der Indexwert von 7 4 ist, da es das fünfte Element im Array ist.

Aber wie kann der Computer den Indexwert der gesuchten Zahl am besten ermitteln?

Zuerst speichern wir die minund max-Werte wie 0und 16.

int min = 0;int max = 16;

Jetzt müssen wir uns eine Vermutung einfallen lassen. Am klügsten wäre es, einen Indexwert in der Mitte des Arrays zu erraten.

Mit dem Indexwert 0 bis 16 in diesem Array wäre der mittlere Indexwert dieses Arrays 8. Das enthält die Zahl 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Unsere Vermutung ist jetzt gleich 8, was 14 im Array ist, da array[8]gleich ist 14.

Wenn die Nummer, die wir suchten, 14 wäre, wären wir fertig!

Da dies nicht der Fall ist, werden wir jetzt die Hälfte des Arrays verwerfen. Dies sind alle Zahlen nach 14 oder der Indexwert 8, da wir wissen, dass 14 größer als 7 ist und unsere Vermutung zu hoch ist.

Nach der ersten Iteration befindet sich unsere Suche nun in: 1, 3, 4, 6, 7, 8, 10, 13

Wir müssen nicht in der letzten Hälfte des ursprünglichen Arrays raten, weil wir wissen, dass all diese Werte zu groß sind. Deshalb ist es wichtig, dass wir die binäre Suche auf eine geordnete Liste anwenden .

Da unsere ursprüngliche Schätzung von 14 größer als 7 war, verringern wir sie jetzt um 1 und speichern sie in max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Jetzt sieht die Suche so aus:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Da unsere Vermutung zu niedrig war, verwerfen wir die untere Hälfte des Arrays, indem wir den Wert erhöhen min, im Gegensatz zu dem, was wir zuvor getan haben max:

min = guess + 1; // min is now 4

Bei der nächsten Iteration bleibt uns Folgendes übrig:

 7, 8, 10, 13min = 4max = 7guess = 5

Da der Indexwert 5 8 zurückgibt, sind wir jetzt eins über unserem Ziel. Wir wiederholen den Vorgang erneut und haben Folgendes übrig:

 7min = 4max = 4guess = 4

Und wir haben nur noch einen Wert, 4, als Index für die gesuchte Zielzahl, nämlich 7.

Der Zweck der binären Suche besteht darin, bei jeder Iteration die Hälfte des Arrays zu entfernen. Wir arbeiten also nur an den Werten, bei denen es sinnvoll ist, weiter zu raten.

Der Pseudocode für diesen Algorithmus würde ungefähr so ​​aussehen:

  1. Let min = 0, und let max = nwhere nist der höchstmögliche Indexwert
  2. Finden Sie den Durchschnitt von minund max, runden Sie ab, so dass es eine ganze Zahl ist. Das ist unserguess
  3. Wenn wir die Zahl erraten haben, hören Sie auf, wir haben sie!
  4. Wenn guesszu niedrig, setzen Sie mingleich eins mehr alsguess
  5. Wenn guesszu hoch, setzen Sie maxgleich eins weniger alsguess
  6. Gehen Sie zurück zu Schritt zwei.

Hier ist eine in C ++ geschriebene Lösung: