>> [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]