>> ROB BOWDEN: Hallo, ich bin Rob.
Wie verwenden wir eine binäre Suche?
Lasst uns herausfinden.
So ist zu beachten, dass diese Suche werden wir rekursiv implementiert.
Sie könnten auch binäre Suche zu implementieren iterativ, also wenn du das getan hast,
das ist völlig in Ordnung.
>> Jetzt lassen Sie uns zuerst daran erinnern, was die Parameter, die Suche werden sollen sein.
Hier sehen wir int-Wert, der ist soll der Wert der Benutzer sein
für die Suche.
Wir sehen die int-Werte-Array, das ist das Array, in dem wir sind
Suche nach Wert.
Und wir sehen, int n, das ist, die Länge der unser Angebot.
>> Jetzt erste, was zuerst.
Wir prüfen, ob n gleich 0 ist, in welcher Fall kehren wir falsch.
Das ist nur zu sagen, wenn wir ein leeres Array-Wert ist eindeutig nicht in ein
leeres Array, so können wir false zurück.
>> Nun wollen wir eigentlich tun, um die binäre Suche Teil der binären Suche.
Also, wollen wir die Mitte finden Element dieses Feldes.
Hier, sagen wir, Mitte gleich n geteilt von 2, da das mittlere Element ist
gehen, um die Länge sein unser Angebot durch 2 geteilt.
Jetzt werden wir zu überprüfen, um zu sehen, ob die Mittelelement gleich dem Wert sind wir
für die Suche.
Also, wenn Werte gleich mitten Wert, wir kann true zurück, da fanden wir das
Wert in unser Angebot.
>> Aber wenn das nicht wahr war, jetzt wir die rekursive tun müssen
Schritt der binären Suche.
Wir müssen entweder die Suche links von der Anordnung oder der
Mitte des Arrays.
So, hier, sagen wir, wenn die Werte in Mitte ist kleiner als der Wert, bedeutet, dass dieser Wert
größer als der Mittel des Arrays.
So muss Wert auf der rechten Seite der sein Element, das wir gerade sah.
>> Also hier werden wir zu Suche rekursiv.
Und wir werden, was wir sind vorbei schauen Um dies in einer Sekunde.
Aber wir werden, um die Suche rechts von dem mittleren Element.
Und in dem anderen Fall, bedeutet das, dass Wert kleiner als der Mitte der war
Array, und so werden wir nach links zu suchen.
Jetzt wird die linke sein wird ein bisschen einfacher, zu betrachten.
So sehen wir hier, dass wir rekursiv Aufruf suchen, wo die erste
Argument ist wieder der Wert wir suchen über.
Das zweite Argument wird sein, die Array, dass wir über die Suche.
Und das letzte Element ist jetzt Mitte.
Denken Sie daran, der letzte Parameter ist unser int n, das ist also die Länge der unser Angebot.
>> In der rekursiven Aufruf zu suchen, wir sind jetzt sagen, daß die Länge der
Array ist Mitte.
Also, wenn unser Angebot war von der Größe 20 und wir bei Index 10 gesucht, da Mitte ist
20 geteilt durch 2, bedeutet, dass wir indem 10 als neuer
Länge unseres Arrays.
Denken Sie daran, dass, wenn Sie ein Array haben der Länge 10, bedeutet, dass die gültige
Elemente sind in den Indizes 0 bis 9 an.
Also das ist genau das, was wir wollen geben unsere aktualisierte Array - die linke
Anordnung aus dem mittleren Element.
>> Also, Blick nach rechts ist ein bisschen schwieriger.
Jetzt lassen Sie uns zuerst betrachten die Länge der Anordnung auf der rechten Seite der
Mittelelement.
Also, wenn unser Angebot war der Größe n, dann ist die neue Array der Größe n minus sein
Mitte minus 1.
Also, lasst uns von n minus Mitte denken.
>> Auch wenn das Array waren von der Größe 20 und wir durch 2 teilen, um die Mitte zu bekommen,
so ist die Mitte 10 ist, dann n minus Mitte wird uns geben, 10, also 10
Elemente auf der rechten Mitte.
Aber wir haben auch diesen minus 1, da wir nicht wollen,
gehören die Mitte selber.
So n minus Mitte minus 1 gibt uns die Gesamtzahl der Elemente rechts
der mittlere Index im Array.
>> Jetzt ist hier zu beachten, dass der mittlere Parameter ist die Array-Werte.
So, hier übergeben wir ein aktualisierten Werte Array.
Diese Werte sowie mittlere plus 1 ist eigentlich sagt rekursiv
Suche, vorbei in einem neuen Array, wo dass neue Array beginnt in der Mitte
plus eine unserer ursprünglichen Werte-Array.
>> Eine alternative Syntax für die, jetzt, Sie begonnen haben, um Zeiger zu sehen, ist
Kaufmanns-Werte Mitte plus 1.
Also, packen Sie die Adresse der Mitte und ein Element der Werte.
>> Nun, wenn Sie nicht zufrieden waren Ändern von Arrays wie die, die Sie
hätte auch dies mit umgesetzt eine rekursive Hilfsfunktion, wo
dass Hilfsfunktion nimmt mehr Argumente.
Anstatt also nur der Wert, desto Anordnung und der Größe des Arrays,
die Hilfsfunktion könnte länger dauern Argumente, einschließlich der unteren Index
Sie würde etwa in der Anordnung Pflege und der obere Index, den Sie kümmern
über die Anordnung.
>> Und so die Verfolgung der beiden unteren Index und der obere Index, brauchen Sie nicht
brauchen, um überhaupt das ändern Originalwerte Array.
Sie können einfach weiter Verwenden Sie die Werte Array.
Aber hier, bemerken wir einen Helfer brauchen nicht funktionieren, solange wir sind
bereit, um die ursprüngliche ändern Werte Array.
Wir sind bereit, übergeben eine aktualisierte Werte.
>> Nun, wir können nicht über binäre Suche ein Array, das unsortiert ist.
Also, lassen Sie uns diese aussortiert.
Nun bemerken, dass Art ist seit zwei Parameter int-Werte, was ist das
Array, das wir sortieren und int n, die die Länge des Arrays ist, dass
wir sortieren.
So, hier umsetzen wollen wir ein Sortieralgorithmus
das ist o n quadriert.
Sie könnten Bubble-Sort, Auswahl wählen Art oder Insertion sortieren oder
eine andere Art haben wir nicht in der Klasse gesehen.
Aber hier werden wir zu gehen Auswahl Art verwenden.
>> Also, wir gehen zu durchlaufen über die gesamte Anordnung.
Nun, hier sehen wir, dass wir die Iteration von 0 bis n minus 1 ist.
Warum nicht den ganzen Weg bis zu n?
Nun, wenn wir bereits sortiert haben die erste n minus 1 Elemente, dann die
letzte Element, was muss schon sein an der richtigen Stelle, so dass die Sortierung über
das gesamte Array.
>> Nun, daran erinnern, wie Auswahl Art funktioniert.
Wir werden über das gesamte Array gehen Suche nach der Minimalwert
und das Array-Stick, am Anfang.
Dann werden wir über die gesamte gehen Array wieder auf der Suche nach der zweiten
kleinste Element, und Stick, in der zweiten Position, in der
Array, und so weiter.
Also, das ist, was dieser tut.
>> Hier sehen wir, dass wir Einstellung der aktuellen Mindest
Wert des i-ten Index.
Also auf der ersten Iteration, wir gehen zu prüfen, der Minimalwert zu sein
der Beginn unserer Array.
Dann werden wir über die laufen Rest der Anordnung, zu überprüfen,
sehen, ob es irgendwelche Elemente kleiner als die, die wir sind momentan
unter Berücksichtigung der Mindest.
>> So, hier sind Werte j plus ein - das ist weniger als das, was wir derzeit
unter Berücksichtigung der Mindest.
Dann werden wir aktualisieren, was wir denken, ist das Minimum, um
Index j plus 1.
Also, dass über die gesamte Array und nach dieser for-Schleife, Mindest
sollte die Mindest Element sein der i-ten Position in der Anordnung.
>> Sobald wir das, wir tauschen kann die Minimalwert in der i-ten Position
in der Anordnung.
Also das ist nur ein Standard-Swap.
Wir speichern in einem temporären Wert - der i-te Wert in der Anordnung -
in die i-te Wert in der Anordnung stellen die Minimalwert, der es angehört,
und dann wieder speichern, in denen die aktuelle Mindestwert verwendet, um die sein
i-te Wert in der Matrix, so dass wir nicht verlieren.
>> So, das weiter auf die nächste Iteration.
Wir werden die Suche nach dem zweiten Minimalwert und legen Sie, dass in der
zweite Position.
Auf der dritten Iteration, wir suchen der dritte Minimalwert und Einsatz
dass in der dritten Position, und so auf, bis wir eine sortierte Array.
Mein Name ist Rob, und dies Auswahl Art war.