[Musikwiedergabe] 

DOUG LLOYD: Alles klar. So ist eine binäre Suche Algorithmus wir verwenden können, um ein Element innerhalb eines Arrays zu finden. Im Gegensatz zu linearen Suche erfordert es ein Sonderbedingung vorher erfüllt werden, aber es ist so viel effizienter, wenn Diese Voraussetzung ist in der Tat erfüllt. 

Also, was ist die Idee hier? es teile und herrsche. Wir wollen die Größe zu reduzieren der Suchbereich um die Hälfte jeder Zeit um eine Zielnummer zu finden. Dies ist, wo diese Bedingung kommt ins Spiel, wenn. Wir können nur die Macht der Hebelwirkung Beseitigung Hälfte der Elemente ohne auch nur anzusehen sie, wenn das Array sortiert. 

Wenn es ein komplettes Missverständnis, Wir können nicht einfach aus der Hand verwerfen die Hälfte der Elemente, weil wir wissen nicht, was wir zu verwerfen. Aber wenn das Array sortiert, wir das tun können, weil wir wissen, dass alles, um die links, wo wir Zeit sind muss niedriger sein als die sein, Wert Wir sind momentan bei. Und alles rund um das rechts, wo wir sind muß grßer sein als der Wert sein, Wir willkommen im. 

Also, was ist der Pseudocode Schritte für die binäre Suche? Wir wiederholen Sie diesen Vorgang, bis der Array oder, wie wir durch gehen, Subarrays, kleinere Stücke das Original-Array ist der Größe 0. Berechnen Sie den Mittelpunkt des aktuellen Unterfeld. 

Wenn der Wert, den Sie suchen, ist in diesem Element des Arrays, zu stoppen. Du hast es gefunden. Das ist großartig. Andernfalls, wenn das Ziel weniger als das, was in der Mitte, so dass, wenn der Wert, den wir schauen, für die niedriger ist als das, was wir sehen, Wiederholen Sie diesen Vorgang wieder, aber ändern Sie den Endpunkt, statt des Seins das Original Ergänzen vollständige Palette, nur auf der linken Seite sein, von denen wir nur sah. 

Wir wussten, dass der mittlere war zu hoch, oder das Ziel war weniger als die Mitte, und so muss sie vorhanden sind, wenn es haupt existiert in dem Array, irgendwo links von der Mitte. Und so werden wir das Array gesetzt Lage, nur nach links des Mittelpunkts als neuer Endpunkt. Umgekehrt, wenn sich das Ziel mehr als das, was in der Mitte, wir genau das gleiche tun, Prozess, sondern wir Ändern Sie den Startpunkt zu sein gerade rechts von der Mitte wir gerade berechnet. Und dann, erneut zu beginnen wir den Prozess. 

Lassen Sie uns dies zu visualisieren, OK? Es gibt also eine Menge los und hier, aber hier ist eine Anordnung der 15 Elemente. Und wir werden sein die Verfolgung von viel mehr Sachen diesmal. So in lineare Suche waren wir nur die Sorge um ein Ziel. Aber dieses Mal wollen wir egal wo wir sind ab zu schauen, wo halten wir suchen, und was ist der Mittelpunkt des aktuellen Array. Also hier haben wir mit binären Suche zu gehen. Wir sind ziemlich gut zu gehen, nicht wahr? Ich werde einfach zu legen hier unten eine Reihe von Indizes. Dies ist im Grunde nur, was Element des Arrays wir reden. Mit linearer Suche, wir kümmern, indem wir müssen wissen, wie viele Elemente wir Iteration über, aber wir wissen nicht wirklich egal, was Element, das wir willkommen im. In binären Suche, wir tun. Und so, die gerade sind es als eine kleine Anleitung. 

So können wir anfangen, oder? Nun, nicht ganz. Denken Sie daran, was ich gesagt habe über binäre Suche? Wir können es nicht auf eine unsortierte Array oder anderes, wir nicht garantieren, dass die bestimmte Elemente oder Werte nicht Versehen verworfen, wenn wir einfach entscheiden Hälfte des Feldes ignorieren. 

So Schritt eins mit binäre Suche ist, müssen Sie eine sortierte Array. Und Sie können jede der Sortier verwenden Algorithmen, die wir gesprochen haben um Sie zu dieser Position zu bekommen. So, jetzt haben wir in einer Position, wo bist wir binäre Suche durchführen. 

Lassen Sie uns also wiederholen Sie den Vorgang Schritt für Schritt, und halten Sie verfolgen, was passiert, wie wir gehen. So ist der erste, was wir tun müssen ist, zu berechnen der Mittelpunkt der aktuellen Array. Nun, wir werden sagen, wir sind in erster Linie Alle, auf der Suche nach dem Wert 19. Wir versuchen, die Nummer 19 zu finden. Das erste Element dieser Array bei Index Null liegt, und das letzte Element dieser Array bei Index 14 entfernt. Und so werden wir diejenigen, Beginn und Ende nennen. 

So berechnen wir die Mittelpunkt durch Hinzufügen 0 plus 14 geteilt durch 2; ziemlich einfach Mittelpunkt. Und wir können sagen, dass der Mittelpunkt ist jetzt 7. So beträgt 15, was wir suchen? Nein, ist es nicht. Wir suchen nach 19 suchen. Aber wir wissen, dass 19 ist größer als das, was wir in der Mitte gefunden. 

Also, was wir tun können, ist Ändern Sie den Startpunkt nur auf der rechten Seite der Be Mittelpunkt und wiederholen Sie den Vorgang. Und wenn wir das tun, haben wir jetzt sagen, dass die neue Startpunkt ist Matrixort 8. Was wir getan haben, ist wirksam ignoriert alles links von 15. Wir haben die Hälfte beseitigt des Problems, und nun, anstatt zu suchen mehr als 15 Elemente in unser Angebot, müssen wir nur über 7 zu suchen. So 8 ist der neue Startpunkt. 14 ist noch der Endpunkt. 

Und nun, über diese gehen wir wieder. Wir berechnen den neuen Mittelpunkt. 8 plus 14 ist 22 geteilt durch 2 ist 11. Ist das, was wir suchen? Nein, ist es nicht. Wir suchen nach einem Wert, der ist auf der Suche weniger als das, was wir gerade gefunden. So werden wir wiederholen der Prozess erneut. Wir gehen, um den Endpunkt zu ändern werden nur auf der linken Seite des Mittelpunktes. So ist die neue Endpunkt wird 10. Und jetzt, das ist der einzige Teil des das Array haben wir zu sortieren. So haben wir nun beseitigt 12 der 15 Elemente. Wir wissen, dass, wenn 19 besteht in der Anordnung, es muss zwischen Element irgendwo vorhanden Nummer 8 und Elementnummer 10. 

So berechnen wir erneut die neue Mittelpunkt. 8 plus 10 ist 18, dividiert durch 2 ist 9. Und in diesem Fall, schauen, Ziel ist in der Mitte. Wir haben genau das, was wir suchen. Wir können aufhören. Wir erfolgreich abgeschlossen eine binäre Suche. Gut. So wissen wir, diesen Algorithmus arbeitet, wenn das Ziel irgendwo innerhalb des Arrays. Hat diesen Algorithmus Arbeit, wenn das Ziel nicht in der Matrix? Nun, lasst uns starten wieder, und diesmal schauen wir uns für das Element 16, die optisch können wir sehen, existiert nirgends in der Anordnung. 

Der Startpunkt ist wieder 0. Der Endpunkt ist wieder 14. Das sind die Indizes des ersten und letzten Elemente des kompletten Arrays. Und wir werden durch den Prozess, den wir einfach gehen ging durch wieder und versuchte, 16 zu finden, obwohl optisch können wir bereits zu sagen, dass es nicht geht, dort zu sein. Wir wollen einfach nur sicher, diesen Algorithmus zu machen wird in der Tat immer noch in irgendeiner Weise zu arbeiten und nicht nur lassen Sie uns in einer Endlosschleife stecken. 

Also, was ist der Schritt ersten? Berechnen Sie den Mittelpunkt des aktuellen Array. Was ist der Mittelpunkt des aktuellen Array? Nun, es ist 7, oder? 14 plus 0 geteilt durch 2 ist 7. Ist 15, was wir suchen? Nein. Es ist ziemlich nahe, aber wir suchen für einen Wert, der etwas größer als das. 

So wissen wir, dass es zu gehen nirgends auf der linken Seite von 15. Das Ziel größer als was ist in der Mitte. Und so setzen wir die neuen Startpunkt zu werden direkt rechts von der Mitte. Der Mittelpunkt ist derzeit 7, so sagen wir, der neue Startpunkt ist 8. Und was wir effektiv haben wieder getan wird ignoriert die gesamte linke Hälfte der Anordnung. 

Jetzt wiederholen wir die bearbeiten ein weiteres Mal. Berechnen Sie den neuen Mittelpunkt. 8 plus 14 ist 22 geteilt durch 2 ist 11. Ist 23, was wir suchen? Leider nein. Wir suchen nach einem Wert suchen dh weniger als 23. Und so in diesem Fall, wir gehen um den Endpunkt zu ändern, um nur sein, links von dem aktuellen Mittenpunkt. Der aktuelle Mittelpunkt ist 11, und so werden wir den neuen Endpunkt zu setzen für das nächste Mal, wenn wir durch diesen Prozess bis 10. 

Auch durch den Prozess gehen wir wieder. Berechnen Sie den Mittelpunkt. 8 plus 10 geteilt durch 2 ist 9. Ist 19, was wir suchen? Leider nein. Wir sind immer noch auf der Suche nach eine Zahl kleiner als die. Also werden wir den Endpunkt dieses Mal ändern nur auf der linken Seite des Mittelpunkts ist. Der Mittelpunkt ist derzeit 9, so der Endpunkt wird 8 sein. Und jetzt sind wir gerade auf der Suche an einem einzelnen Element-Array. 

Was ist der Mittelpunkt dieses Arrays? Nun, es beginnt bei 8, es endet bei 8, der Mittelpunkt 8. Ist das, was wir suchen? Sind wir auf der Suche nach 17? Nein, wir für 16 suchen. So dass, wenn es in der Anordnung vorhanden ist, es muss irgendwo vorhanden links von dem wir gegenwärtig sind. Also, was sollen wir tun? Nun, wir werden den Endpunkt setzen, gerecht zu sein links von dem aktuellen Mittenpunkt. Also werden wir den Endpunkt bis 7 zu ändern. Wissen Sie, was gerade zu sehen ist hier passiert, wenn? Schlagen Sie jetzt hier. 

Starten Sie jetzt größer als Ende. Wirksam, wobei die beiden Enden der unser Angebot überquert haben, und der Startpunkt Jetzt nach dem Endpunkt. Nun, das tut nicht keinen Sinn, nicht wahr? So, jetzt, was wir sagen können ist, dass wir eine Unter Array der Größe 0. Und wenn wir zu bekommen Nun können wir uns jetzt garantieren, dass Element 16 nicht in der Matrix vorhanden sind, da der Startpunkt und Endpunkt haben gekreuzt. Und so ist es nicht da. Nun beachtet, dass es sich leicht anders als der Startpunkt und Ende weisen die gleiche ist. Wenn wir waren auf der Suche für 17, müsste in der Anordnung, und der Startpunkt gewesen und Endpunkt dieser letzten Iteration bevor diese Punkte überquerte, würden wir dort gefunden haben 17. Es ist nur, wenn sie sich kreuzen, wir können gewährleistet, dass das Element nicht existieren in der Anordnung. 

Werfen wir also viel weniger Schritte als lineare Suche. Im schlimmsten Fall, wir hatten zu zerlegen und eine Liste mit n Elementen mehrmals in der Mitte, um das Ziel zu finden, entweder weil das Zielelement werden irgendwo in der letzte sein Division oder es überhaupt nicht existieren. Also im ungünstigsten Fall müssen wir spalten die array-- wissen Sie das? Log von n-mal; wir haben, um das Problem zu schneiden Hälfte eine bestimmte Anzahl von Malen. Das Mal ist log n. 

Was ist der beste-Case-Szenario? Nun, das erste Mal, Berechnung des Mittelpunkts, wir finden, was wir suchen. In allen vorherigen Beispiele für binäre Suche wir haben etwas mehr gegangen, wenn wir wurde für das Element 15 auf der Suche, wir würden das sofort gefunden. Das war ganz am Anfang. Das war der Mittelpunkt der erste Versuch einer Spaltung einer Division in binäre Suche. 

Und so im schlimmsten Fall binäre Suche läuft in log n, die wesentlich besser ist, als lineare Suche, im schlimmsten Fall. Im besten Fall, binäre Suche läuft an Omega von 1. So binäre Suche ist viel besser als lineare Suche, aber Sie müssen mit dem Prozess der tun haben Sortieren Sie Ihre Array zuerst, bevor Sie Nutzen Sie die Macht der binären Suche. 

Ich bin Doug Lloyd. Dies CS 50.