[MUSIC SPIEL] ZAMYLA CHAN: Das erste, was Sie vielleicht Hinweis zu finden, ist, dass wir bereits Code haben für uns geschrieben. Dies wird Verteilung Code bezeichnet. So werden wir nicht nur schreiben unsere eigenen Code von Grund auf mehr. Vielmehr sind wir in den Hohlräumen Füllung in einigen bereits bestehenden Code. Die find.c Programm fordert für Zahlen um den Heuhaufen zu füllen, sucht das Heuschober für einen Benutzer vorgelegt Nadel, und es tut dies, indem Art und Suche, Funktionen definiert in helpers.c. So find.c ist bereits geschrieben. Ihre Aufgabe ist es, Helfer zu schreiben. Also, was tun wir? Wir sind der Umsetzung zwei Funktionen. Suche, die true zurückgibt, wenn ein Wert wird im Heuhaufen gefunden, der Rückkehr false, wenn der Wert nicht im Heuhaufen. Und dann sind wir auch die Umsetzung sortieren die sortiert die Array namens Werte. Also lassen Sie uns Suche anzugehen. Suche ist derzeit als ein umgesetzt lineare Suche, aber man kann viel tun, besser als die. Lineare Suche ist in O umgesetzt n Zeit, die ziemlich langsam ist. Obwohl, kann es zu suchen jede Liste, um sie gegeben. Ihre Aufgabe ist es, binäre Suche zu implementieren, die Zeit von O log n ausgeführt wurde. Das ist ziemlich schnell. Aber es gibt eine Bedingung. Binäre Suche kann nur suchen durch vorsortiert Listen. Warum ist das so? Nun schauen wir uns ein Beispiel an. Da ein Array von Werten, die Heuhaufen, wir gehen auf der Suche für eine Nadel. Und in diesem Beispiel, die ganze Zahl drei ist. Die Art und Weise, dass binäre Suche funktioniert ist, dass Vergleichen wir den mittleren Wert von das Array an der Nadel, ähnlich wie, wie eröffneten wir ein Telefonbuch in der Mitte Seite in Woche null. Also nach dem Vergleich der Mittelwert die Nadel, die Sie entweder zu verwerfen kann die linke oder die rechte Hälfte der Anordnung durch Anziehen Ihre Grenzen. In diesem Fall wird, da drei unserer Nadel, weniger als 10, der mittlere Wert, der Recht gebunden ist, zu verringern. Aber versuchen Sie, Ihre Grenzen zu machen so fest wie möglich. Wenn der mittlere Wert ist nicht die Nadel, dann wissen Sie, dass Sie nicht brauchen, um schließen sie in Ihrer Suche. So haben Sie Recht gebunden sind können ziehen Sie die Suche haft nur ein kleines bisschen mehr, und so weiter und so fort, bis Sie finden Ihre Nadel. Also, was hat der Pseudocode aussehen? Nun, während wir noch auf der Suche durch die Liste und haben immer noch Elemente Blick in nehmen wir die Mitte der Liste, und zu vergleichen, dass die mittlere Wert unsere Nadel. Wenn sie gleich sind, dann ist das bedeutet, wir haben gefunden, die Nadel und wir können return true. Andernfalls, wenn die Nadel kleiner als der mittlere Wert, dann bedeutet, dass wir kann die rechte Hälfte verwerfen und nur suchen Sie die linke Seite des Feldes. Sonst werden wir suchen die rechten Seite der Anordnung. Und am Ende, wenn Sie keine haben mehr Elemente von links nach suchen, aber Sie nicht Ihre Nadel noch nicht gefunden, dann false zurück, da die Nadel definitiv nicht im Heuhaufen. Jetzt eine nette Sache über diese Pseudo in binären Suche ist, dass es sein kann entweder als ein iteratives interpretiert oder rekursive Implementierung. So wäre es, wenn Sie rekursiv aufgerufen die Suchfunktion im Such funktionieren auf jeder Hälfte des Feldes. Wir werden Rekursion ein bisschen später in der Abdeckung Natürlich aber weiß, dass es ein Option, wenn Sie möchten, um zu versuchen. Jetzt schauen wir uns sortieren. Sortieren nimmt ein Array und den ganzzahligen n, der die Größe des Arrays ist. Nun gibt es verschiedene Arten der Art, und Sie können einige sehen Shorts für Demos und Erklärungen. Der Rückgabetyp für unsere Sortierfunktion ist nichtig. Das heißt also, dass wir nicht um jede Art von Array zurück. Wir sind eigentlich vor sich geht, die sehr verändern Array, das in uns übergeben wurde. Und das ist möglich, weil Arrays sind durch Bezugnahme in C geleitet Jetzt werden wir siehe dazu später mehr, aber die wesentliche Unterschied zwischen Tod in so etwas wie einer ganzen Zahl und Weitergabe in einer Anordnung, dass, wenn man Pass in einer ganzen Zahl, ist gerade dabei, C eine Kopie dieser integer und übergeben es an die Funktion. Die ursprüngliche Variable wird nicht geändert sobald die Funktion beendet. Mit einer Anordnung, auf der anderen Seite, ist es nicht, um eine Kopie zu machen, und Sie werden tatsächlich werden die Bearbeitung der Array selbst sehr. So eine Art der Sortierung ist die Auswahl sortieren. Die Auswahl funktioniert durch die Art ab der Anfang, und dann können Sie laufen über und finden Sie das kleinste Element. Und dann tauschen die kleinste Element mit dem ersten. Und dann auf das zweite Element bewegen , Finden Sie die nächstkleinere Element, und dann tauschen, dass mit dem zweite Element in dem Array, weil das erste Element bereits sortiert. Und so dann können Sie für jede weiter Element bei der Identifizierung der kleinsten Wert und tauschen es aus. Denn ich gleich 0 ist, das erste Element n minus 1, Sie gehen zu vergleichen sind jeder nächste Wert danach und finden der Index des minimalen Wert. Sobald Sie den Mindestwert-Index zu finden, Sie können diesen Wert von Array tauschen Mindest-und Array I. Eine andere Art der Art, dass man implementieren ist Bubble-Sort. So Bubble Sort durchläuft der Liste Vergleich benachbarter Elemente und Vertauschen der Elemente, die sind in der falschen Reihenfolge. Und auf diese Weise, das größte Element Blase wird bis zum Ende. Und die Liste wird einmal nicht mehr sortiert Elemente wurden ausgetauscht. Das sind also zwei Beispiele für die Art Algorithmen, die Sie umsetzen können der Fund-Programm. Sobald Sie fertig zu sortieren, und Sie haben Suche gemacht, fertig. Mein Name ist Zamyla, und dies ist CS50. [MUSIC SPIEL]