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.