Datenstruktur und Algorithmen Binäre Suche

Die binäre Suche ist ein schneller Suchalgorithmus mit einer Laufzeitkomplexität von Ο (log n). Dieser Suchalgorithmus arbeitet nach dem Prinzip des Teilens und Eroberens. Damit dieser Algorithmus ordnungsgemäß funktioniert, sollte die Datenerfassung in sortierter Form erfolgen.

Bei der binären Suche wird nach einem bestimmten Element gesucht, indem das mittlere Element der Sammlung verglichen wird. Wenn eine Übereinstimmung auftritt, wird der Index des Elements zurückgegeben. Wenn das mittlere Element größer als das Element ist, wird das Element im Unterarray links vom mittleren Element gesucht. Andernfalls wird das Element im Unterarray rechts neben dem mittleren Element gesucht. Dieser Prozess wird auch auf dem Subarray fortgesetzt, bis die Größe des Subarrays auf Null reduziert ist.

Wie funktioniert die binäre Suche?

Damit eine binäre Suche funktioniert, muss das Zielarray sortiert werden. Wir werden den Prozess der binären Suche anhand eines Bildbeispiels lernen. Das Folgende ist unser sortiertes Array und wir nehmen an, dass wir die Position des Werts 31 mithilfe der binären Suche suchen müssen.

Zuerst werden wir die Hälfte des Arrays mit dieser Formel bestimmen -

mid = low + (high - low) / 2

Hier ist es 0 + (9 - 0) / 2 = 4 (ganzzahliger Wert von 4,5). 4 ist also die Mitte des Arrays.

Jetzt vergleichen wir den an Position 4 gespeicherten Wert mit dem gesuchten Wert, dh 31. Wir stellen fest, dass der Wert an Position 4 27 ist, was nicht übereinstimmt. Da der Wert größer als 27 ist und wir ein sortiertes Array haben, wissen wir auch, dass der Zielwert im oberen Teil des Arrays liegen muss.

Wir ändern unser Tief auf Mittel + 1 und finden den neuen Mittelwert wieder.

low = mid + 1
mid = low + (high - low) / 2

Unsere neue Mitte ist jetzt 7. Wir vergleichen den an Position 7 gespeicherten Wert mit unserem Zielwert 31.

Der an Position 7 gespeicherte Wert stimmt nicht überein, sondern ist mehr als das, wonach wir suchen. Der Wert muss sich also im unteren Teil von dieser Stelle befinden.

Daher berechnen wir die Mitte erneut. Diesmal ist es 5.

Wir vergleichen den an Position 5 gespeicherten Wert mit unserem Zielwert. Wir finden, dass es ein Match ist.

Wir schließen daraus, dass der Zielwert 31 an Position 5 gespeichert ist.

Die binäre Suche halbiert die durchsuchbaren Elemente und reduziert so die Anzahl der durchzuführenden Vergleiche auf sehr wenige Zahlen.

Pseudocode

Der Pseudocode von binären Suchalgorithmen sollte folgendermaßen aussehen:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Klicken Sie hier , um Informationen zur Implementierung der binären Suche mit einem Array in der Programmiersprache C zu erhalten .