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 zu sortieren, die sortiert die Array namens Werte. Also lassen Sie uns Suche anzugehen. 

Suche wird derzeit umgesetzt als eine lineare Suche. Aber Sie tun können, viel besser als die. Lineare Suche ist in O n umgesetzt Zeit, die ziemlich langsam ist, obwohl es können jede Liste, um sie zu suchen 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 eine Nadel, und in diesem beispielsweise die ganze Zahl 3. 

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 0. 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, da 3, unsere Nadel ist weniger als 10, der mittlere Wert, 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. Also Ihr Recht gebunden anziehen kann die Suche haft nur ein kleines bisschen mehr, und so weiter und so fort, bis Sie finden Ihre Nadel. 

Also, was bedeutet das Pseudo- Code aussehen? Nun, während wir immer noch durch Blick die Liste und haben immer noch Elemente zu sehen in, nehmen wir den mittleren der Liste und vergleichen Sie das Mittelwert für unsere Nadel. Wenn sie gleich sind, dann ist das bedeutet, wir haben fand 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 zu 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 auf jeden Fall ist nicht im Heuhaufen. 

Jetzt, ein nette Sache über dieses Pseudo Code in binäre Suche ist, dass es möglich entweder als ein iteratives auszulegen oder rekursive Implementierung. So wäre es, wenn Sie rekursiv aufgerufen die Suchfunktion im Such funktionieren auf jeder Hälfte des Feldes. Wir werden ein bisschen decken Rekursion später in den Kurs. Aber wissen, dass es ist eine Option wenn Sie möchten, um zu versuchen.