BINARY SEARCH Algorithm (Java, C), Algorithmen und Datenstrukturen

Zurück ◈ Weiter

Benötigen Sie eine Programmieraufgabe helfen? Erschwinglicher Programmierung Hausaufgaben zu helfen.

Im Allgemeinen einen Wert in unsortierten Array zu finden, sollten wir eins nach dem anderen Elemente eines Arrays durchschauen, bis gesuchte Wert gefunden wird. Im Fall des gesuchten Wertes von Array nicht vorhanden ist, gehen wir durch alle Elemente. Im Durchschnitt sind die Komplexität eines solchen Algorithmus ist auf die Länge des Arrays proportional.

Situation ändert sich deutlich, wenn Array sortiert ist. Wenn wir es, eine Direktzugriffsfähigkeit wissen sehr effizient durchsucht Wert genutzt wird schnell zu finden. Kostenalgorithmus des Suchens reduziert sich auf binären Logarithmus der Feldlänge. Als Referenz log2 (1 000 000) ≈ 20. Das bedeutet, dass im schlimmsten Fall. Algorithmus macht 20 Stufen einen Wert im sortierten Array von einer Million Elementen zu finden oder zu sagen, dass es nicht das Array Nicht bestimmt.

Algorithmus ist recht einfach. Es kann entweder rekursiv oder iterativ durchgeführt werden:

  1. erhalten das mittlere Element;
  2. wenn das mittlere Element zum gesuchten Wert entspricht, stoppt der Algorithmus;
  3. Andernfalls sind zwei Fälle möglich:
    • gesucht Wert kleiner als das mittlere Element. In diesem Fall geht zu dem Schritt 1 für den Teil der Anordnung, bevor mittleres Element.
    • gesucht Wert größer als das mittlere Element. In diesem Fall geht zu dem Schritt 1 für den Teil der Anordnung, nach dem Mittelelement.
Jetzt sollten wir definieren, wenn Iterationen stoppen sollte. Erster Fall ist, wenn gesuchte Element gefunden wird. Zweite ist, wenn Sub-Array keine Elemente hat. In diesem Fall können wir schließen, dass Wert gesucht stellt nicht in der Anordnung.

Schritt 1 (mittleres Element 19> 6): 6 18 -1 5 19 25 46 78 102 114

Schritt 2 (mittleres Element 5 < 6): -1 5 6 18 19 25 46 78 102 114

Schritt 3 (mittleres Element 6 == 6): 6 18 -1 5 19 25 46 78 102 114

Schritt 1 (mittleres Element 19 < 103): -1 5 6 18 19 25 46 78 102 114

Schritt 2 (mittleres Element 78 < 103): -1 5 6 18 19 25 46 78 102 114

Schritt 3 (mittleres Element 102 < 103): -1 5 6 18 19 25 46 78 102 114

Schritt 4 (mittleres Element 114> 103): 6 18 -1 5 19 25 46 78 102 114

Schritt 5 (gesuchter Wert fehlt): 6 18 -1 5 19 25 46 78 102 114

Komplexitätsanalyse

Sehr großer Vorteil dieses Algorithmus ist, dass es die Komplexität auf der Array-Größe im schlimmsten Fall logarithmisch abhängig ist. In der Praxis bedeutet dies, tut, dass Algorithmus höchstens log2 (n) Iterationen, die auch für großen Arrays eine sehr kleine Zahl ist. Es kann sehr leicht nachgewiesen werden. Tatsächlich auf jedem Schritt der Größe des gesuchten Teils wird um die Hälfte reduziert. Algorithmus stoppt, wenn es keine Elemente in die Suche daher in ganzen Zahlen folgende Ungleichheit zu lösen.:

n / 2 Iterationen> 0

Iterationen <= log2 (n).

Es bedeutet, dass binäre Suchalgorithmus Zeitkomplexität O (log 2 (n)).

Code Ausschnitte.

Sie können rekursive Lösung für Java und iterative für C ++ siehe unten.

* Suche nach einem Wert in sortiertes Array

In Verbindung stehende Artikel

Zurück ◈ Weiter