Binäre Suche – eine der einfachsten Möglichkeiten, um ein Element in einem Array zu finden

Oft Programmierer, auch Anfänger, mit der Tatsache konfrontiert, dass es eine Reihe von Zahlen, die eine bestimmte Anzahl finden müssen. Es ist diese Sammlung wird ein Array bezeichnet. Und finden Artikel drin, gibt es eine Vielzahl von Möglichkeiten. Aber die einfachste von ihnen kann eine binäre Suche auf dem rechten Seite in Betracht gezogen werden. Was ist diese Methode? Und wie binäre Suche zu implementieren? Pascal ist die einfachste Umgebung für die Organisation eines solchen Programms, so dass wir es verwenden, um zu studieren.

Zuerst analysieren, was die Vorteile dieser Methode sind, ist es so können wir verstehen, was ist der Punkt in der Studie des Themas. So lassen Sie uns mit einer Abmessung von mindestens 100000000 Elemente eine Anordnung haben, die einige finden müssen. Natürlich kann dieses Problem leicht durch eine einfache lineare Suche gelöst werden, in dem wir den Zyklus verwenden wird das gewünschte Element mit all denen, die im Array vergleichen. Das Problem ist, dass die Umsetzung dieser Idee wird zu viel Zeit in Anspruch nehmen. In einem einfachen Pascal-Programm in mehrere Behandlungen und drei Zeilen des Haupttextes, Sie werden es nicht bemerken, aber wenn wir auf ein mehr oder weniger große Projekte mit einer großen Anzahl von Filialen und guter Funktionalität kommen, wird das Programm bereit sein, zu lange geladen werden. Vor allem, wenn der Computer eine schwache Leistung. Daher gibt es eine binäre Suche, die mindestens zweimal die Suchzeit reduziert.

Also, was ist das Arbeitsprinzip dieser Methode? Ab sofort soll es sagen, dass binäre Suche funktioniert, ist nicht in jedem Array, sondern nur auf einer sortierten Reihe von Zahlen. Bei jedem Schritt mittleren Elemente des Arrays aufgenommen (dh die Nummer des Elements). Wenn die erforderliche Zahl größer ist der Durchschnitt, dann alles , was übrig ist, dass weniger als die durchschnittliche Zelle ist, kann verworfen werden und nicht dort zu suchen. Umgekehrt, wenn weniger als der Durchschnitt – unter diesen Zahlen rechts, können Sie nicht suchen. Wählen Sie dann einen neuen Suchbereich, in dem das erste Element wird das mittlere Element des gesamten Arrays, und der letzte und der letzte Wille. Die durchschnittliche Anzahl der neuen Feld ¼ des gesamten Segment sein, das (die letzte Element + dem mittleren Element des gesamten Arrays) / 2 ist. Wiederum wird die gleiche Operation durchgeführt – einen Vergleich mit der durchschnittlichen Anzahl des Arrays. Wenn der Sollwert kleiner als der Durchschnitt, lehnen wir die rechte Seite, und auch als nächstes zu tun, bis jetzt das mittlere Element nicht erwünscht wäre.

Natürlich ist es am besten an einem Beispiel zu sehen, wie binäre Suche zu schreiben. Pascal hier wird jeder Anzug – Version ist nicht wichtig. Nehmen wir ein einfaches Programm schreiben.

Es ist eine Reihe von 1 bis h unter der Bezeichnung „Massiv“, eine Variable, die die untere Begrenzung der Suche anzeigt, genannt „Niz“, die obere Grenze, die so genannte „verh“, das durchschnittliche Suchwort – „sredn“; und die erforderliche Anzahl – „isk“.

Also, zuerst wir die obere und untere Grenze des Bereichssuche zuordnen:

Niz: = 1;
verh: = h + 1;

Dann organisieren den Zyklus „bis der Boden geringer ist als die obere Grenze“:

Während niz <verh – 1 do
beginnen

Bei jedem Schritt unterteilen wir das Segment 2:

sredn: = (Niz + verh) div 2; {Use die Funktion div, weil die ohne Rest divide}

Jedes Mal der Bewertung. Da der Artikel bereits gefunden wurde, wenn das Medium gewünscht wird, unterbrechen Zyklus:

іf sredn = isk dann brechen;

Wenn das mittlere Element des Arrays mehr als gewünscht ist, die linke Seite verwerfen, das heißt, benennen die obere Grenze der mittleren Element:

wenn MASSIV [sredn]> isk dann verh: = sredn;

Und wenn im Gegenteil, es macht die untere Grenze:

sonst niz: = sredn;
Ende;

Das ist alles, was im Programm sein wird.

Lassen Sie uns überlegen, wie sie die binäre Methode in der Praxis aussehen wird. Betrachten dieses Array: 1, 3, 5, 7, 10, 12, 18, und es wird die Nummer 12 sucht.

Insgesamt haben wir sieben Elemente, so wird das vierte Medium, der Wert 7.

Seit mehr als 12, 7, 1,3 und 5 Elementen, können wir verwerfen. Dann haben wir die Zahl 4, 4/2 kein Rückstand erhielt ist 2. So wird ein neues Element im Durchschnitt 10 sein wird.

Da 12 größer als 10 ist, verwerfen wir 7. 10, 12 und 18 bleibt.

Hier ist das mittlere Element ist bereits 12, ist es die erforderliche Anzahl. Diese Aufgabe wird abgeschlossen – Nummer 12 gefunden.