[Powered by Google Translate] [Abschnitt 3] [weniger komfortabel]
>> [Nate Hardison] [Harvard University]
>> [Dies ist CS50.] [CS50.TV]
>> Alles klar, lasst uns loslegen.
Willkommen in Woche 4 der CS50.
Wenn euch öffnen Sie einen Webbrowser und öffnen pset 3,
Scramble mit CS50, werden wir beginnen werde
durch den Abschnitt von Fragen gibt.
Genau wie letzte Woche, werden wir in CS50 Spaces arbeiten,
wenn du auch ziehen, dass als gut,
und wenn Sie voran gehen und besuchen Sie diesen Link, ich habe hier oben an der Spitze.
Es ist Zeit, um loszulegen.
Wir haben unser kleines hallo Programm hier. Nichts verrückt.
Eines der ersten Dinge, die ich will mit euch tun, ist heute gehen über ein paar Lösungen
zum Problem Set 1, Art B. Lösungen,
nur so können Sie ein Gefühl dafür bekommen, welche Arten von Codeteilung schreibt,
welche Arten von Code anderen Studenten sind Schreiben,
und haben Sie einen Blick auf sie, weil ich weiß, es ist komisch
wenn Sie übermitteln eine Lösung für ein Problem, set-und get Kommentare
auf eigene Version, aber manchmal ist es hilfreich zu sehen, wie andere Leute es getan hat,
vor allem diejenigen, die nett sind suchen.
Zum größten Teil, ich war wirklich mit den Lösungen, die euch produziert beeindruckt.
Ich habe noch nicht angefangen, bei Ihrem Problem Set 2s, aber wenn sie so etwas wie die erste,
es bedeutet nur Gutes.
>> Wenn Sie auf meine Revisionen sehen, beginnen wir den ganzen Weg hinunter auf Revision 1,
und wir werden, um einen schnellen Blick auf eine Mario-Lösung zu nehmen.
Wenn Sie diese nach oben ziehen, sind diese Programme, dass wir gehen zu präsentieren korrekt.
Es gab keine Korrektheit Probleme mit diesen Problemen, sondern
wollen wir ein wenig über die verschiedenen Design-Themen zu sprechen
Das waren hier zum Einsatz.
Eines der Dinge, die interessant war über die Lösung
ist, dass es dieses neue Konstrukt namens Pfund definieren verwendet,
manchmal auch als ein Hash definieren bezeichnet.
Lassen Sie mich zoomen Sie es hier.
A # define können Sie die Namen auf diese Zahlen in Ihrem Programm zu geben.
In diesem Fall ist die maximale Höhe der Pyramide in Mario
wurde 23 und und anstatt 23 in meinem Code-
wir würden, dass so hart Codierung 23 beziehen -
Statt dies gibt den Namen MAX_HEIGHT zu dieser Nummer,
, so dass sich hier in meinem do-while-Schleife
Sie können tatsächlich MAX_HEIGHT beziehen
anstatt die Nummer 23 in.
[Student] Was ist der Vorteil, das zu tun?
Das ist eine große Frage.
Einer ist die Lesbarkeit.
Ein Vorteil der Verwendung dieses # define die Lesbarkeit.
Wenn ich lese diesen Code, kann ich sehen, was los ist.
>> Ich kann in diesem Zustand sehen, dass wir testen
für die Höhe ist <0, die wir auch definiert haben könnte
eine minimale Höhe oder eine min Höhe.
Der andere Vorteil ist, dass ich dann lesen Sie den Rest der Zeile zu sehen
dass wir auch die Überprüfung, um sicherzustellen, dass die Höhe nicht größer ist als die maximale Höhe,
da werden wir fortsetzen, während die Höhe größer ist als die maximale Höhe.
Der andere Vorteil ist, wenn ich zoomen ein bisschen hier-
wenn ich dieses Programm und ich führen Sie es, sagen wir, mit 23 gerade jetzt,
Es gibt alle 23 Zeilen einfach so.
Aber sagen wollte ich die max Höhe zu ändern,
und jetzt will ich die maximale Höhe der Pyramiden zu begrenzen
nur sagen-Mann, das flippige war.
# Include, # define MAX_HEIGHT,
und lassen Sie uns sagen, dass wir wollten es gleich 10 gesetzt.
An diesem Punkt war alles, was ich zu tun hatte, ändern Sie es in diesem einen Standort.
Ich kann den Code neu kompilieren, und jetzt, wenn ich versuche, in 12 geben,
es wird Sie auffordern mich wieder.
In diesem Fall sind wir nur mit MAX_HEIGHT einmal.
Es ist nicht so große Mühe zu gehen
und ändern Sie es in der while-Schleife, wenn Sie benötigen.
Aber in Programme, wo man sich auf die gleiche magische Zahl sind
immer und immer wieder, diese # define-Mechanismus ist wirklich praktisch
weil Sie nur ändern, einmal am Anfang der Datei-it ist in der Regel, wo du sie-
und die Änderung sickert durch den Rest der Datei.
>> Andere Dinge, die ich wollte in dieser Zuordnung beachten Sie, dass ich dachte, sah wirklich schön,
war die Benennung der Variablen.
Sie sehen hier, dass wir Integer-Variablen als Zeilen-und genannte Höhe haben.
Spaces, Hashes, hilft es, den Code ein wenig mehr lesbar,
macht es ein wenig besser verständlich, was eigentlich vor sich geht.
Dies steht im Gegensatz zur Verwendung von, sagen wir, Zufallsbuchstaben
oder einfach nur Kauderwelsch insgesamt.
Eine letzte Sache, ich darauf hinweisen müssen, ist, dass in for-Schleifen,
oft sind diese Iteratorvariablen, diese Zähler, die Sie verwenden in Ihrem for-Schleifen,
Es ist Standard und üblich, sie entweder mit i und dann j beginnen und dann k
und gehen von dort aus, wenn Sie mehr Variablen müssen,
und dies ist nur eine Konvention.
Es gibt viele Konventionen.
Es hängt von der Programmiersprache Sie verwenden.
Aber in C, wir beginnen üblicherweise mit i.
Es macht keinen Sinn zu verwenden, sagen wir, a oder b
je nach Situation.
Das ist es für diese ein.
Wenn Sie ziehen nun Revision 2, werden Sie sehen, ein weiteres Mario,
und dieses ist ähnlich zu dem anderen, dass wir gerade gesehen,
aber es tut etwas irgendwie cool.
Wenn wir in diesem Bereich hier zu sehen in der inneren for-Schleife,
sie sind mit ein paar verrückte suchen Syntax hier rechts in dieser Zeile.
Dies nennt man eine ternäre Operator.
Es ist eine if else-Anweisung in einer Zeile zusammengefasst.
Die Bedingung ist dieser Teil in Klammern.
Es ist gleichbedeutend mit der Aussage, wenn j <height - i - 1.
Und dann, was der Inhalt, dass, wenn Block wäre es der Raum
und dann die Inhalte dessen, was der andere wäre es diese #.
Es ist im Wesentlichen die Zuordnung einen Raum, um diese Variable.
Es Putting einen Platz in den Inhalt des Blocks variable,
wenn diese Bedingung erfüllt ist, und wenn die Bedingung nicht erfüllt ist,
dann wird der Block Variable erhält this #.
Und dann, natürlich, anstatt den Aufbau eines gesamten Strings
und Drucken alles am Ende diese Lösung druckt sie ein Zeichen in einer Zeit.
Pretty cool.
>> Noch ein paar Dinge zu sehen. Wir fahren Sie mit gierig.
Nun, wenn wir gierig schauen, diese erste Lösung
nutzt diese # definiert eine ganze Menge.
Wir haben ein Konstante für jede der unterschiedlichen Zahlen in dieser Programm definiert.
Wir haben eine für Cent pro Dollar, eine für die Quartale, Groschen, Nickels und Pfennige,
und jetzt, wenn wir nach unten scrollen und lesen Sie den Code,
können wir sehen, ein Standard-do-while-Schleife Druck alles aus.
Art der Kern dieses Problem wurde klar, dass
Sie benötigt, um den Schwimmer zu konvertieren, dass Sie in vom Benutzer zu lesen, um eine ganze
genau die Mathematik zu tun, und das ist, weil
mit Fließkommazahlen, wie wir darüber gesprochen in der Vorlesung kurz
es ist nicht möglich, genau zu repräsentieren jeden einzelnen Wert auf der Zahlengeraden
denn es gibt unendlich viele Werte zwischen 3 und, sagen wir, 3,1 sogar.
Sie können 3,01 und 3,001 und 3,0001, und Sie können weitermachen.
Es stellt sich heraus, wenn Sie mit dem Geld arbeiten, Sie wollen oft zu konvertieren
in Integer-Format, so dass Sie nicht verlieren Pfennige und solche Sachen.
Dadurch, dass und Rundung war der Schlüssel.
Diese Lösung verwendet eine vollkommen unkompliziert, große Algorithmus
die dekrementiert die Anzahl der Cent übrig, zuerst durch Quartalen
dann durch Groschen, dann Nickels, dann durch ein paar Cent,
und Addieren der Anzahl von Münzen jeder Zeit.
>> Eine andere Lösung, dass wir sehen, wie ich zoomen und gehen Sie zu Revision 4,
hatte eine sehr ähnliche Beginn, sondern verwendet div und mod
hier drüben für die Berechnung der Anzahl der Cent.
Dies ist die Anzahl von Vierteln gleich der Anzahl von Cents durch 25 geteilt,
und der Grund, das funktioniert, weil wir zu tun Ganzzahldivision sind,
so ist es zu verwerfen jegliche Reste.
[Student] Haben wir die Suche kommentieren?
Es hängt wirklich davon.
[Student] Du kommentieren mehr als Code direkt hier.
Ja, und so gibt es eine Reihe von unterschiedlichen Philosophien zu diesem Thema.
Meine persönliche Philosophie ist, dass Ihr Code ist wirklich die Wahrheit,
wie Ihr Code ist, was tatsächlich ausgeführt auf dem Computer,
und so sollte der Code so lesbar wie möglich, nicht so viele Kommentare erfordern.
Das heißt, wenn Sie Dinge tun, die Art sind schwierig mathematisch
oder algorithmisch, es ist gut für diejenigen, so dass Sie kommentieren
eine zusätzliche Dimension, eine zusätzliche Schicht wer liest den Code.
In diesen Lösungen oft sind sie stärker, nur weil kommentierte
Wir wollen in der Lage sein, sie zu verteilen und haben die Menschen abholen
und lesen sie ziemlich leicht.
Aber auf jeden Fall würde ich zustimmen, dass dies schwer ist.
[Student] Aber wenn Sie Zweifel haben, gehen Sie schwerer?
Wenn Sie Zweifel haben, gehen schwerer.
Einige Leute werden sagen manchmal return 0 oder so ähnlich.
Ich denke, das ist eine lächerliche Kommentar.
Klar, dass ist das, was passiert ist.
Ich brauche nicht Deutsch zu mir sagen.
Manchmal sind die Leute schreibt Sachen wie "kthxbai!"
Das ist irgendwie süß, aber auch nicht-
das ist nicht so den Unterschied zwischen kommentieren Punkte oder nicht.
Diese Art von Kommentaren sind nur ha, ha.
Cool.
>> An dieser Stelle wollen wir die Arbeit an dem Problem Set 3 Abschnitt Fragen.
Wenn euch ziehen diese wieder auf,
wie letzte Woche, werden wir nicht die Shorts in diesem Abschnitt zu sehen.
Wir lassen euch tun, dass auf Ihrer eigenen Zeit und sprechen über die Fragen.
Aber jetzt in diesem Abschnitt werden wir ein wenig mehr Zeit damit verbringen,
sprechen weniger von den kodierenden Grundlagen
wie wir letzte Woche getan hat, und stattdessen werden wir mehr konzentrieren
ein bisschen mehr der Theorie, so reden binäre Suche und dann sortieren.
Von diejenigen, die verfolgt haben zusammen mit dem Vortrag,
kann mir jemand eine Zusammenfassung von dem, was der Unterschied ist
zwischen Binär-Suche und lineare Suche?
Was ist los? Sure.
Lineare Suche durchsucht jedes Element in der sortierten Liste
nacheinander durch eine nach der anderen durch ein,
und binäre Suche teilt die Liste in zwei Gruppen,
prüft, ob der Schlüssel-Wert, dass Sie für die Suche ist größer oder kleiner als der Mittelpunkt-Wert
dass Sie gerade gefunden, und wenn es weniger als ist, geht es mit der unteren Liste
und teilt sich dann noch einmal, hat die gleiche Funktion
ganz nach unten bis er die Mitte findet, daß sie gleich dem Wert sich.
Right.
>> Warum kümmern wir uns?
Warum wir über binäre Suche Vergleich lineare Suche reden?
Yeah.
Binary ist viel schneller, wenn Sie die Größe des Problems verdoppeln
es dauert noch ein Schritt eher als doppelt so viele.
Genau.
Das ist eine tolle Antwort.
Lineare Suche ist sehr Überprüfung ein Element zu einem Zeitpunkt,
und als wir sahen, schon am ersten Tag der Vorlesung
wenn David ging durch seinen Telefonbuch Beispiel
und herausgerissen eine Seite des Telefonbuchs zu einer Zeit,
und hielt dabei, dass immer und immer und immer wieder,
es wird nehmen ihn eine wirklich lange Zeit mit niemandem im Telefonbuch zu finden,
es sei denn natürlich, er suche jemanden ganz am Anfang des Alphabets.
Mit binären Suche, können Sie viel schneller gehen,
und es ist nicht nur doppelt so schnell oder 3 mal so schnell oder 4 mal so schnell.
Aber das Problem immer kleiner und kleiner viel schneller.
Um dies zu veranschaulichen, werden wir darüber zu reden, was los ist
wenn wir binäre Suche schreiben.
Das Problem bei der Hand ist, dass wenn ich eine Reihe von Zahlen,
dh 1, 2, 3, 5, 7, 23, 45, 78, 12.323,
und dann 9 mit einer Tonne von 0s nach,
Wir wollen in der Lage sein, um herauszufinden, wirklich schnell, was in
Dieses Array von Zahlen.
Ich weiß, das scheint ein wenig albern und ein wenig gekünstelt,
denn im Moment ist es.
Wir haben ein Array, das nicht sehr viele Elemente in ihr,
und wenn ich einer von euch fragen, um herauszufinden, ob
23 ist in dem Array, können Sie das ziemlich schnell tun
nur durch einen Blick auf diese und sagt mir ja oder nein.
Der analoge zu prüfen, ist vorstellbar, wenn diese, sagen wir,
eine Excel-Tabelle mit 10.000 Zeilen, 20.000 Zeilen.
Natürlich können Sie den Befehl F oder die Kontrolle F und schauen etwas.
Sie können auch die Filter und die Suche stuff,
aber wenn Sie mussten durch diese Datei Zeile für Zeile für Zeile suchen,
es würde Sie eine lange Zeit, es zu finden.
Es ist ein bisschen wie im Telefonbuch beispielsweise auch, wo
niemand schaut durch ein Telefonbuch einer Seite zu einem Zeitpunkt.
Typischerweise haben sie ihn in der Mitte zu öffnen,
oder in dem Fall einer Vielzahl von Telefondiensten Pfund und Wörterbücher, wo
Sie tatsächlich haben es auf den ersten Buchstaben eingegeben haben,
Sie weiter zur ersten Buchstaben umdrehen und öffnen und durchlaufen dort.
>> Erinnern mich an deinen Namen wieder. >> Sam.
Sam.
Wie Sam sagte, ist, dass lineare Suchprozess wird wirklich langsam,
und stattdessen mit binären Suche ist der Weg das funktioniert, dass
jedes Mal, wenn wir durch eine Iteration der Suchalgorithmus,
wir gehen, um die Liste in der Hälfte teilen, im Wesentlichen
in zwei kleinere Listen.
Und dann auf der nächsten Iteration der Schleife, werden wir es wieder trennen
in andere kleinere Listen.
Wie Sie sehen können, hält das Problem immer kleiner
denn wir halten Verwerfen Hälfte der Liste jede einzelne Zeit.
Wie funktioniert das discard Arbeit?
Nur zur Erinnerung, was wir tun, wenn wir einen Computer waren
und wir waren, sagen wir, auf der Suche nach der Nummer 5 in dieser Liste
ist, dass wir eine Zahl in der Mitte holen.
In der Mitte dieser Liste, denn es sind 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Zahlen,
würden wir die Zahl entweder am vierten Position oder an der fünften Position holen,
und wir nennen würde, dass die Mitte unserer Liste.
Pick-Nummer in Mitte.
Dann, genau wie Sam sagte, wir testen, um zu sehen, ob diese Zahl ist gleich
die Zahl, die wir erhalten möchten oder unsere gewünschte Nummer.
Wenn er gleich ist, dann haben wir es gefunden. Wir gewinnen.
Wenn es nicht gleich, dann gibt es ein paar Fälle.
Die zwei Fälle sind entweder die Anzahl größer als die Anzahl Wir denken beispielsweise hat,
oder es ist weniger als.
Wenn es größer ist, werden wir nach rechts zu bewegen.
Und wenn es weniger ist, bewegen wir uns auf der linken Seite.
Und dann wiederholen wir den ganzen Prozess
entweder auf der rechten Hälfte oder der linken Hälfte der Liste.
>> Das erste Problem in der heutigen Abschnitts ist es, herauszufinden,
wie können wir tatsächlich beginnen, dies in C-Code auszudrücken.
Wir haben den Pseudocode hier.
Was fangen wir tun, ist Ich ziehe einen brand-neuen Raum,
speichern Sie diese Revision, so dass wir diese Hinweise für haben später
wir löschen alles, und dann kopieren und aus dem Problem-Set
diese Informationen in unsere Räume, und hoffentlich nicht zu brechen.
Perfect.
Wenn ihr all das zu tun, kopieren und fügen Sie diesen Code in Ihren neuen Raum,
in ein leeres ein.
Lassen Sie uns versuchen Daniel. Wenn Sie kompilieren und ausführen dieses Programms funktioniert es?
Nein >> Wie ist es da?
Er sagt, die Steuerung erreicht Ende einer Nicht-void-Funktion.
Yeah, so lassen Sie mich versuchen Sie es.
Habt ihr das schon mal gesehen? Weißt du, was das bedeutet?
Okay, lasst uns sezieren diese ein wenig.
Es ist bei file.c sagen on line 9, Spalte 1 haben wir einen Fehler haben, genau wie du gesagt hast,
und er sagt, dass es von dem Fehler Warnung und dem Rückgabetyp Warnung stammen.
Es sieht aus wie etwas los ist mit dem Rückgabetyp, was Sinn macht.
Wir haben eine nicht-void-Funktion, was bedeutet, dass wir haben eine Funktion
das bedeutet nicht void zurückgeben.
Ein Hohlraum ist eine Funktion, die wie folgt aussieht:
void foo (), und es ist nichtig, weil der Rückgabetyp void,
was bedeutet, dass, wenn wir etwas hier
wie return 1, würden wir einen Compiler-Fehler für diese.
Allerdings haben wir eine nicht-void-Funktion.
Unsere nicht-void-Funktion ist in diesem Fall unsere Suchfunktion
weil es eine Rückgabetyp bool.
Wenn es zu sagen, dass die Steuerung das Ende eines nicht-void Funktion erreicht,
es ist, weil search keinen return-Anweisung.
Es ist nicht wieder alles vom Typ bool.
>> Wir beheben können, dass und was denkt ihr
Suche sollte standardmäßig zurückkehren?
Was sollte die Standard-Rückgabewert der Suche sein?
Denn das ist, was wir am Ende zu setzen.
Charlotte, haben Sie any-?
Wahr oder falsch? >> Wahr oder falsch.
Welche?
Falsch. Ich weiß nicht.
False? Lass es uns versuchen.
Warum sagst du return false? Das ist toll Intuition.
[Charlotte] Ich weiß es nicht.
Wir werden wieder in diesem Fall falsch, weil dies unser Standard sein wird
wenn aus irgendeinem Grund die Liste leer ist oder die Nadel
dass wir für die ist leider nicht vorhanden.
Dann ganz am Ende, wenn wir nicht wahr früher wieder in dieser Funktion
wissen wir immer, dass diese Funktion sage Nein, es ist nicht im Array.
Es ist nicht im Heuhaufen.
Wenn wir nun kompilieren und ausführen it-lass mich speichern Sie diese, so dass wir es nach oben ziehen.
Wenn wir nun kompilieren und ausführen unserem Programm, es baut.
Wir bekommen unsere kleinen prompt.
Wenn ich getroffen 4-uh-oh.
Es hat überhaupt nichts aus. Es sieht aus wie alles endete okay.
Wir haben dies in. füllen
Wir sprachen über den Algorithmus in Pseudocode ein wenig vor.
Lassen Sie mich sehen, speichern Sie diese,
und ich werde diesen Algorithmus zurück ziehen wieder an.
Lassen Sie uns treffen diesen Kerl. Nope.
Da ist es.
Wie machen wir das?
Was wäre eine gute Strategie für das Anfahren diesen Code sein?
Sie müssen eine Zahl in der Mitte holen.
Wie holen wir eine Zahl in der Mitte eines Feldes?
Irgendwelche Vorschläge?
[Student] strlen durch 2 geteilt.
Strlen durch 2 geteilt. Das ist ein großer.
Strlen arbeitet mit speziellen Arten von Arrays.
Welche Arten von Arrays?
String-Arrays, Zeichen-Arrays.
Es ist die gleiche Art von Konzept, das wir anwenden möchten,
aber wir können nicht strlen, weil wir nicht über ein Array von Zeichen.
Wir haben eine Reihe von ints.
Aber was bedeutet strlen für uns?
Weißt du, was es für uns bekommt?
[Student] strlen bringt uns die Länge.
Genau, es wird uns die Länge.
Strlen bekommt die Länge des Arrays für uns.
>> Wie bekommen wir, dass in unserer binäre Suche Programm?
Wie würden Sie die Länge eines Arrays?
[Student] strlen?
Sie können die Länge eines korrekt formatiert C-String Array mit strlen bekommen.
Das Problem ist allerdings, dass wir nicht mit einem String-Array.
Wenn wir wieder in diesem Code aussehen, haben wir diese Integer-Array.
Woher wissen wir, wie lange es ist?
[Student] Gibt es ein Äquivalent eines für Endpunkt, wie int l, oder was?
Es stellt sich heraus es tatsächlich nicht, und dies in einer Weise, ist dies
eines jener Dinge, die einfach ist gut, über C wissen,
dass es keine Möglichkeit gibt, um die Länge eines Arrays zu erhalten
wenn alles, was ich geben kann ist das Array.
Der Grund, es funktioniert mit Streichern, der Grund strlen Werke,
Denn wenn ein String ist richtig formatiert,
es wird dieses spezielle \ 0 Zeichen am Ende haben.
>> Sie können sich auch vorstellen, wenn Sie eine falsch formatierte Zeichenfolge haben
und es gibt keine \ 0 Zeichen gibt, dann ist die ganze Sache nicht funktioniert.
[Student] Können Sie das \ 0?
Wir könnten in diesem Fall.
Wir könnten hinzufügen, irgendeine Art von \ 0
oder irgendeine Art von bedeutet Charakter und dann verwenden Sie diese.
Aber das ist nicht ganz zur Arbeit gehen
weil die \ 0 ist für einen char-Typ,
und hier haben wir ints.
Die andere Sache ist, wenn wir einen besonderen Wert nutzen konnten
wie -1 zu markieren das Ende eines Arrays
dann könnten wir nie speichern eine -1 in unserer Integer-Arrays.
Wir würden geklebt werden.
Es stellt sich heraus, dass der einzige Weg, um die Länge zu bekommen
einer Anordnung in C ist, um tatsächlich daran erinnern
Wenn Sie es einrichten und dann weiterzugeben, um mit dem Array
so dass, wenn ich eine Funktion haben, die gehen einige Arbeit zu tun ist
auf einem Array von ganzen Zahlen oder Schwimmer oder verdoppelt oder was haben Sie,
Ich muss auch geben die Funktion die Array-Länge,
und das ist genau das, was wir hier in der Suche-Funktion.
Wenn Sie schauen, was wir getan haben, wenn wir in unser Angebot hier vorbei,
wir auch in der Länge, die Größe passieren.
Es passiert einfach, dass wir diese Variable namens hier
dieser Parameter oder Argument.
Dies ist eine Funktion die Liste der Argumente oder Parameter-Liste genannt wird,
und diese werden auch als Argumente oder Parameter.
Menschen verwenden unterschiedliche Begriffe zu unterschiedlichen Zeiten.
Ich habe manchmal vertauschen sie selber.
Es passiert einfach so, dass diese Variable hier ebenfalls genannt wird
dies # define hier oben.
Aber sie sind nicht das Gleiche.
Die Kapitalisierung nicht egal.
>> Wenn man sieht, was hier passiert, schauen, erklären wir
unserer int-Array, das wir nannten Zahlen haben.
Wir haben ihm unsere Größe, die unsere # define an der Spitze entspricht.
Es wird 8 sein.
Und dann, wenn wir rufen Sie dann unsere Suchfunktion unten,
passieren wir die Zahl wollen wir suchen, was wir dazu aufgefordert werden,
bekommen vom Benutzer.
Wir passieren im Array, diese Zahlen,
und dann müssen wir auch in der Größe der Anordnung vorbei,
und dann der Wert der Größe 8 wird gespeichert
oder auf diese Integer-Variable namens Größe übergeben.
Wir haben die Größe des Arrays.
Wenn wir nun zurück zu dem, was wir über früher reden,
Ich denke, Missy brachte den Punkt, dass, was wir brauchten zu tun ist, die Länge des Arrays
und teilen sie durch 2, und das wird uns den Mittelpunkt.
Mal sehen.
Kann ich jemanden schreibe dies und speichern Sie sie in ihrem Raum?
Wie wäre es mit Leila?
Kann ich Ihnen schreibe diese in?
Schreiben Sie die erste Zeile, wo Sie die Länge des Arrays zu nehmen und den Mittelpunkt
und speichern Sie es in einer neuen Variable.
Ich gebe Ihnen ein paar Sekunden. Sind Sie bereit?
[Schüler unhörbar]
Klar, konnte ich berechnen Sie den Mittelpunkt
den Heuhaufen Array innerhalb der Suchfunktion
über die Länge des Heuhaufen Array, das ist der Größe variabel?
Nichts tricky hier.
[Leila] Just Größe / 2 und just-
Und speichern Sie sie, und klicken Sie auf die Schaltfläche Speichern hier an der Spitze,
und wir nach oben ziehen.
Perfect.
Dort gehen wir. Awesome.
>> Wie es aussieht, wird dies zu kompilieren?
[Leila] Nein, muss es höher zu sein.
[Nate] Ja, so was brauchen wir tun?
[Leila] Wie int Mittelpunkt oder so etwas.
Awesome. Ja, lasst uns das tun, int Mittelpunkt = Größe.
Wird diese kompilieren?
Lassen Sie löschen diesen Kommentar und bekommen es aus dem Weg.
Was wird darüber nicht kompilieren?
Wir machen nicht alles mit integer,
so müssen wir es oder etwas Ähnliches zu drucken.
Ja, genau.
Wir kriegen eine unbenutzte Variablen.
Was wird nicht über das funktionieren?
Ich glaube, Sie sagten etwas, Sam. Semikolon.
Ja, ich bin fehlen diese Semikolon.
Es wird ein konstanter was im Laufe der Laufzeit sein.
Das letzte, was ich tun werde ist werde ich etwas Leerraum auf beiden Seiten gelegt
dieses Operators hier, da die in der Regel ist, wie wir es tun
nach unseren Styleguide.
Wir haben den Mittelpunkt unserer Array.
Wenn wir nun zurück zu unserem Algorithmus erinnern,
was war der zweite Schritt, den wir tun, wenn wir den Mittelpunkt gehabt haben?
[Student] Wenn er größer ist [unverständlich].
Ja, so haben wir eine Art von Vergleich zu tun, und was vergleichen wir hier?
Du hast gesagt, wenn er größer als ist. Was ist in diesem Satz auf?
Die Zahl, die aufkommt, wenn es das ist größer als der Mittelpunkt, dann gehen Sie zu dem Array?
Genau, so die Zahl, die kommt, wenn wir-
Die Nadel, so dass wir an der Nadel Vergleichen,
und was machen wir den Vergleich gegen die Nadel?
Da die Nadel ist das, was wir suchen.
Wir Vergleich mit dem Mittelpunkt zu bekommen.
>> Aber macht es Sinn, zu überprüfen, um zu sehen,
wenn die Nadel legen = Mittelpunkt?
Macht das Sinn?
Hat jemand widersprechen?
Geben wir es zu versuchen, wenn (Nadel == Mittelpunkt).
[Student] Sie printf Sie es gefunden.
[Nate] printf ("Wir fanden es \ n");
Ansonsten-ich bin bald anfangen etwas anderes zu tun hier.
Ich werde damit beginnen, Klammern um if-Anweisungen die ganze Zeit
nur weil, wenn wir mehr Zeug, dann
bekommen wir nicht die Compiler.
Ja, Sam. Du hast einen Punkt.
Das Problem ist, dass ein Mittelpunkt Position in der Anordnung repräsentiert,
aber man kann es um den Wert in dieser Position des Arrays darstellen.
Das ist ein großer Punkt.
Haben alle hören, was Sam gesagt hat?
Er sagte, dass Mittelpunkt wie
stellt nur eine Position in der Anordnung, aber es ist nicht die eigentliche Element in dem Array.
Wenn Sie darüber nachdenken, den Code so geschrieben gerade jetzt,
wenn wir dieses Array hier unten aussehen, hat die 8 Elemente in ihr,
was ist der Wert des Mittelpunktes würde in dieser Funktion sein?
[Student] 4.
[Nate] 4.
Wenn wir uns für die Zahl 4 -
und wir können nur diesen Code ausführen und legte ein kleines trauriges Gesicht hier
weil wir es nicht finden, wenn wir diesen Code ausführen
wie gerade jetzt, Hochladen, Gebäude, lassen Sie mich nach unten scrollen,
und wenn wir für die Zahl 4,
fanden wir es, aber wir haben nicht dies printf ja.
Ein Grund dafür ist, dass wir nicht wieder wahr,
aber wir haben wirklich die Nummer 4?
Und Sam ist nicht selbstverständlich.
Was haben wir zu finden?
Wir fanden den Mittelpunkt, die, wenn wir uns mit dem Array hier unten,
es geht um das Element mit dem Index 4, dass wir auf der Suche,
welches 23.
>> Wie können wir tatsächlich das Element in der Mitte
und nicht nur der Mittelpunkt selbst?
[Student] Wir würden uns geben char oder so etwas?
Was würde das tun, nur aus Neugier?
Können Sie erarbeiten ein wenig mehr?
Sie haben, um die Position in der Zahl zu verwandeln,
so mußt du um irgendeine Verbindung, ich glaube, es ist char, aber es könnte nicht sein.
Ja, das ist ein guter Punkt.
Wir haben dabei eine Menge dieser Umwandlung Positionen in Zeichen, diese Zeichen,
in den ersten beiden Problem-Sets.
Es stellt sich heraus, dass hier das fast ähnlich ist
Zugriff auf das i-te Zeichen in einem String, wenn das Sinn macht.
Hier wollen wir den Mittelpunkt Element zugreifen.
Wie machen wir das?
Kevin, haben Sie irgendwelche Vorschläge, wie wir das tun könnte?
Sie könnten Heuhaufen zu tun, geschlossen offen Halterung, Mitte, Halterung.
Können Sie das für uns?
Speichern Sie es hier, und wir werden diesen nach oben ziehen.
Wir in dieser Zeile 9 suchen,
und wir erkennen, dass wir nicht wollen, um die Nadel in der Mitte zu vergleichen,
sondern, wir wollen, um die Nadel zu vergleichen
auf das Element an Position Mittelpunkt in unserem Heuhaufen Array.
Cool.
Dort gehen wir.
Ja, das sieht ziemlich gut, wenn (Nadel == Heuhaufen [Mittelpunkt]).
Wir fanden es.
Nun, wenn wir den Code ausführen-wir kommen wieder ein wenig bit-
kompiliert, es läuft, und jetzt, wenn wir uns für 4,
wir haben es nicht finden, weil wir jetzt eigentlich immer sind die Nummer 23.
Wir bekommen den Wert 23, und das ist, was wir für unsere Nadel verglichen.
Aber das ist gut. Das ist ein Schritt in die richtige Richtung.
>> Das ist, was wir zu tun versuchen.
Wir versuchen nicht, die Nadel gegen Positionen im Array vergleichen
sondern gegen die eigentlichen Elemente im Array.
Wenn wir wieder schauen nun auf den nächsten Schritt in unserem Algorithmus,
Was ist der nächste Schritt?
Leila bereits erwähnt sie kurz.
[Student] Überprüfen Sie, ob sie größer oder kleiner als ist und dann entscheiden, welchen Weg sich zu bewegen.
[Nate] Ja, das würde so, wie wir das tun?
Kann man in einem gewissen-Ich legte speichern Sie diese Revision,
und dann, wenn Sie setzen in einigen Linien, die das tun wird.
Yeah, Charlotte. >> Ich habe eine Frage.
Sollte es nicht Mittelpunkt sein - 1, da die erste Sache ist,
es ist 0 indiziert, so dass, wenn wir 4 gesetzt, das ist eigentlich nicht der Charakter, den wir suchen?
Ja, und das andere Problem mit diesem ist-
Das ist ein großer Fang, denn was wird am Ende geschieht möglicherweise
wenn wir uns bewegen und halten wir nicht immer zunächst einstellen?
Ich denke, was wir am Ende tut zuzugreifen versucht
das Element an der achten Position des Arrays,
die in diesem Fall nicht vorhanden.
Wir wollen eine Art der Bilanzierung von der Tatsache zu tun
dass wir einige Null-Indizierung.
[Charlotte] Sorry, ich meinte Mittelpunkt - 1 in den eckigen Klammern.
Wir können das tun.
Wir kommen auf diese Frage zurückzukommen in nur ein bisschen.
Sobald wir beginnen, auf die tatsächliche Looping zu bekommen,
das ist, wenn wir wirklich sehen, diese ins Spiel kommen.
Zur Zeit können wir dies tun, aber du bist völlig richtig.
Das Null-Indizierung wird eine Wirkung, die wir zur Rechenschaft ziehen müssen.
Mal sehen.
>> Wie ist die größer und kleiner als-?
[Student] ich, wie die größer und kleiner als Teil tun.
Ich war mir nicht sicher, was zu drucken, wenn Sie, dass es weniger als Heuhaufen Mittelpunkt oder größer ist als zu finden.
Hier kann ich retten, was ich habe-
[Nate] Ja, wenn Sie sparen, was du hast, und wir werden es nach oben ziehen.
Dort gehen wir.
[Student] Und ich legte Fragezeichen für das, was ich nicht wusste.
[Nate] Das sieht gut aus.
Hier haben wir Fragezeichen haben, weil wir noch nicht wissen,
was wir ganz noch nicht.
Was würden wir tun wollen-oops, wir haben einige Klammern alle funky auf uns.
Wir korrigieren diese Klammern.
Dort gehen wir.
Und was wollen wir tun, nach unserem Algorithmus,
wenn wir nicht finden die Nadel?
Sprich im Fall, dass die Nadel weniger als das, was wir sehen, ist. Kevin.
Nur an der linken Hälfte zu suchen.
Richtig, also wir stellen einen Kommentar hier, der sagt "am linken Hälfte sehen."
Und wenn die Nadel größer ist als der Heuhaufen in der Mitte, was wir tun wollen?
[Student] Dann auf der rechten Hälfte zu suchen.
Schauen Sie sich die rechte Hälfte "an rechten Hälfte sehen."
Nicht zu schäbig.
Okay, so an diesem Punkt, sieht es ziemlich gut.
Das Problem mit dem Code geschrieben ist, was als?
[Student] Sie haben noch Endpunkte für den Hälften.
Richtig, wir haben keine Endpunkte für den Hälften.
Wir sind auch nur gehen, um durch diese sofort gehen.
Wir sind nur gehen, um ein Mittelpunkt zu suchen.
Entweder das Element da ist, oder es ist nicht.
Um dies zu bewerkstelligen, müssen wir irgendeine Art von Wiederholung zu tun.
Wir müssen immer wiederholen, bis wir feststellen, dass
entweder das Element in dort, weil wir nach unten und habe verengt es dann endlich gefunden,
oder es ist nicht da, weil wir durch all die Dinge sah
in den entsprechenden Hälften der Anordnung und festgestellt, dass nichts vorhanden ist.
>> Wann immer wir haben diese Wiederholung los ist, was machen wir zu benutzen?
[Student] Eine Schleife.
Irgendeine Art von Schleife. Ja.
[Student] Können wir eine do-while-Schleife und haben es tun, und dann, während
die Nadel nicht gleich-ich bin nicht sicher, wo ich mit, dass geht.
Aber Art wie das tun, solange er nicht gleich dem Wert, den die Benutzereingabe.
Yeah, also schauen wir mal, wie könnte dies selbst schreiben?
Du hast gesagt, verwenden wir eine do-while-Schleife.
Woher kommt das tun, start?
[Student] Gleich nach der Größe / 2.
[Nate] Okay, und was sollen wir tun?
Wir werden in der Zeit später zu füllen.
Was sollen wir tun?
[Student] Wollen wir nicht alle das Zeug haben wir in der if Teil?
[Nate] Mögen all dieses Zeug, great.
Copy und Paste.
Oh, man.
Mal sehen, ob das funktioniert, wenn wir können tab dieses vorbei.
Beautiful.
Okay, und wir speichern Sie diese, so dass Sie Jungs es haben.
Alles klar, und wir werden dies tun, während-
was war das, während Bedingung, die Sie nach waren?
[Student] Während die Nadel nicht gleich, so wie das Ausrufezeichen.
Aber ich bin nicht sicher, was genau das noch ist.
[Nate] Ja, das ist ein Weg, es zu tun.
Sam, hast du einen Kommentar?
[Sam] Ich erinnerte mich, als ich die Videos sah,
Ich nahm einen Screenshot von einer der-artigen, wenn wir den Pseudocode tat für sie,
es gab einige Beziehung zwischen max und min.
Ich denke, es war so etwas wie, wenn max ist immer weniger als min.
Got it.
[Sam] Oder wie wenn max nicht weniger als min oder so ähnlich,
denn das würde bedeuten, dass Sie alles, was gesucht.
>> Ja, so wie sieht es max und min wurden beziehe klingen?
[Sam] Werte, die-ganze Zahlen, die sich ändern werden
bezogen auf wo wir den Mittelpunkt.
Genau.
[Sam] An diesem Punkt ist es [unverständlich] Berechnung der max und min. Gehen
Midpoint ist max und min Idee.
Macht das Sinn, um die Leute?
Wenn wir beginnen, wie werden wir diese Iteration tun hatten,
Sie sind völlig richtig, dass wir irgendeine Art von do-while-Schleife verwenden möchten.
Aber ich denke, wenn wir uns erinnern, was passiert an der Stelle dieses Arrays
und was tatsächlich passiert-ich bin nun schreiben hier-
bei der ersten Iteration der binären Suche, haben-wir
Ich werde b und e verwenden, um den Anfang zu bezeichnen.
Und dann das Ende unserer Array.
Wir wissen, dass der Anfang bei 4 rechts ist hier drüben,
und wir wissen, dass das Ende bei 108 ist.
Sagen, dass wir für die Zahl 15 suchen.
Das erste Mal, dass wir dies tun, wie wir gesehen haben,
der Mittelpunkt ist entweder zu 16 oder 23 zu sein
je nachdem, wie berechnen wir die Dinge aus.
Da gleichmäßig geteilt in der Mitte würde uns diesen Raum
zwischen 16 und 23, können wir nicht gleichmäßig teilen sie
oder teilen und Sie erhalten in einem echten Mittelpunkt.
Wir bei 16 aussehen.
Wir werden erkennen, "Hey, 16> 15, dass wir suchen."
Um dann bei der linken Hälfte des Arrays aussehen
was wir am Ende tun, ist zu verwerfen
Dieses gesamte obere Abschnitt
und sagen: "Okay, jetzt unsere Endpunkt wird hier sein."
Die nächste Iteration der Schleife, wir jetzt nach diesem Array
effektiv mit diesen Teil verworfen, weil jetzt
wenn wir unter den Mittelpunkt, um die Differenz zwischen dem Anfang und dem Ende,
finden wir unsere Mitte zu 8 betragen,
die können wir dann testen 8 zu sehen, wo es in Bezug auf die Zahl, die wir suchen, ist,
15, finden Sie, dass 15 größer ist,
so müssen wir auf dem rechten Teil der Liste zu verschieben,
denen wir wissen, weil wir Menschen sind, und wir können es sehen.
Wir wissen, dass der rechte Teil sein wird, wo wir es finden,
aber der Computer nicht weiß, dass, so, was wir tun wir eigentlich
haben diese gehen, und jetzt der Anfang und das Ende
sind die gleichen Stelle, so der Mittelpunkt wird die einzige Nummer in der Liste an diesem Punkt,
die ist 15, und wir haben es gefunden.
Heißt das etwas Licht auf, wo diese ganze max und min-Notation wird,
Verfolgen von den Endpunkten des Arrays, um herauszufinden
how, um gezieltere Dinge nach unten?
>> Was würde passieren, wenn das nicht gleich 15 jetzt?
Was, wenn wir für 15 und stattdessen suchten, waren diese Zahl auch 16?
Wir würden sagen, "Oh, er größer ist.
Wir wollen zurück nach links. "
Und wir würden unsere E nach rechts zu bewegen,
An diesem Punkt haben wir einen Endpunkt, der in Konflikt würde.
Es wäre nicht in der Lage, für jede mehrere Elemente durchsuchen
denn jetzt haben wir unsere Endpunkt und unseren Anfangspunkt,
unsere max und unsere min, sind jetzt umgedreht.
Wir durch das gesamte Array zu suchen. Wir können nichts finden.
Das ist der Punkt, an dem wir sagen wollen: "Okay, wir werden diesen Algorithmus stoppen würde.
Wir haben nichts gefunden. Wir wissen, dass es hier nicht. "
Wie soll das?
[Student] Wie genau funktioniert der Computer automatisch das Ende?
Wie funktioniert das Ende am Ende vor dem Anfang?
Das Ende endet vor Beginn
wegen der Mathematik, dass wir gehen jedes Mal tun wir dies tun.
Die Art und Weise wir tauschen ist, wenn man sich das erste Mal sehen wir diese Swap tun
wo wir den Anfang bei 4 und das Ende
den ganzen Weg hinunter auf 108 und unser Mittelpunkt, sagen wir, bei 16 -
Ich werde diese wieder zurückzusetzen 15-wenn wir für die 15 suchen,
wir wussten, dass das, was wir, wenn wir die 16 geprüft habe und sah, dass es größer war
und wollte die ganze rechte Teil der Liste zu verwerfen,
sahen wir, dass das, was wir tun wollten, ist diese E hier bewegen.
Effektiv wurde die E zu einem vor der Mitte bewegt.
Ebenso, wenn wir machten diese Iteration des Algorithmus
und der Mittelpunkt war 8,
wir festgestellt, dass 8 <15, so dass wir die b bewegen wollte
ein hinter dem Mittelpunkt.
Nun sind der Anfang und das Ende sowohl miteinander an diesem 15.
>> Wenn wir würden geschehen, um einen anderen Wert, nicht 15 sehen,
oder, wenn dies 15 hatte statt eine 16,
würden wir festgestellt, dass die e wir ein, bevor der Mitte verschieben wollen haben.
Nun ist die e wäre es klappte weniger als die b.
Lassen Sie uns durch, wie wir tatsächlich am Ende Kodierung diesen Algorithmus zu gehen.
Wir wissen, dass wir diesen Mittelpunkt Berechnung haben wollen.
Wir wissen auch, dass wir den Anfang und das Ende des Arrays verfolgen möchten
unserer aktuellen Array, so dass wir herausfinden können,
wo diese linke Hälfte der Liste ist und wo die rechte Hälfte der Liste ist.
Wir tun das entweder mit Anfang und Ende,
oder wir können sie min und max.
Ich benutze beginnen und enden diese Zeit.
Wenn wir anfangen, wenn wir blicken zurück auf unser Beispiel hier unten,
unseren Anfängen wurde an den Anfang des Arrays gesetzt, wie natürlich.
Welche Index war das? Was sollte unsere beginnen?
Daniel.
[Daniel] Haystack [0].
[Nate] Yeah, so könnten wir es gleich Heuhaufen [0].
Das Problem ist jedoch, dass dies nicht gibt uns die Position des ersten Elements.
Es gibt uns den Index des ersten Elementes oder dem tatsächlichen Wert an dieser ersten Position befindet.
[Student] Das wird zu 0,20 konvertieren?
[Nate] Was wird dies tun wird-gut, es wird nichts Verarbeitung.
Was wird es tun, ist es eine 4 in beginnen zu speichern,
und dann wird es schwer sein, Vergleiche mit Beginn machen
weil begin werden Halten des Wertes von 4,
das ist der Beginn unseres Array,
aber wir wollen die Indizes im Array zu verfolgen
im Gegensatz zu den Werten entgegengesetzt.
Wir eigentlich eine 0, so.
Für das Ende des Array-Charlotte brachte diese bis ein wenig früher.
Dies ist, wo wir berücksichtigen nehme die Null Indizierung.
>> Charlotte, was ist das Ende des Arrays?
Was ist der Index des Endes?
[Charlotte] Size - 1.
Ja, und welche Größe sollten wir verwenden?
Sollten wir Kapital Größe oder Kleinbuchstaben Größe?
Kapital Größe.
In diesem Fall könnten wir Kapital Größe.
Wenn wir wollten diese Funktion tragbar sein
und verwenden Sie diese Funktion in anderen Programmen
können wir tatsächlich nutzen Kleinbuchstaben Größe.
Es ist auch in Ordnung.
Aber Charlotte ist völlig richtig, dass wir die Größe haben wollen - 1.
An diesem Punkt-
[Student] Wie ist es, dass Sie Großbuchstaben Größe zu verwenden?
Wie kommt es, dass wir in Großbuchstaben Größe zu verwenden?
Es stellt sich heraus, dass diese # definiert sind wirklich,
unter der Haube, finden Sie einen Text wie und zu ersetzen, wenn das Sinn macht.
Wenn Sie Ihren Code zu kompilieren, der Vorlaufphase
der Compiler durchläuft der Datei,
und es sieht für überall, dass Sie Kapital Größe geschrieben,
und ersetzt den Text buchstäblich mit einer 8, einfach so.
In diesem Sinne ist etwas ganz anderes als eine Variable.
Es dauert nicht keinen Platz im Speicher.
Es ist ein einfaches Text zu ersetzen Trick.
In diesem Fall werden wir Größe zu verwenden.
Von hier aus wollen, um irgendeine Art von Wiederholung zu tun,
und wir sind auf dem richtigen Weg mit unserer do-while-Schleife.
Wir wollen etwas tun, bis eine Bedingung nicht mehr zu halten,
und wie wir bereits gesehen haben, sahen wir, dass diese Bedingung
war in der Tat, dass wir nicht wollen, das Ende
kleiner sein als das zu beginnen.
>> Dies ist unser Stoppbedingung.
Wenn dies der Fall ist, wollen wir stoppen und wie erklären "Hey, wir haben nichts gefunden."
Um dies auszudrücken, wollen wir eine Art Schleife verwenden.
In diesem Fall würde es sich um eine do-while-Schleife sein, eine for-Schleife, eine while-Schleife?
Wir haben eine do-while-Schleife hier.
Sie Kerle wie dieser Ansatz?
Meinst du, wir sollten einen anderen Ansatz zu versuchen?
Kevin, alle Gedanken?
Wir könnten eine while-Schleife, weil wir wissen, maximale
größer wäre als min an den Start sowieso.
Ja, es gibt also keine Initialisierung, geschehen muss.
Diese do-while-Schleifen sind toll, wenn Sie etwas zu initialisieren
bevor dann testen, wobei hier
wir wissen, dass wir nicht zu halten Reinitialisierung beginnen und enden
jeder Runde der Schleife.
Wir wissen, dass wir sie initialisieren möchten, dann besuchen Sie unsere Bedingung.
In diesem Fall werde ich tatsächlich mit einem einfachen while-Schleife gehen.
Es stellt sich heraus, dass do-while-Schleifen relativ selten verwendet werden.
Viele Orte haben nicht einmal lehren, while-Schleifen.
Sie sind gut für den Umgang mit Benutzereingaben, so haben wir eine Menge von ihnen bisher gesehen.
Aber normal und while-Schleifen sind viel häufiger.
Es stellt sich heraus, dass diese Bedingung als schriftliche
nicht wirklich tun uns viel Gutes, und warum ist das so?
Es tut mir leid, ich weiß nicht, Ihren Namen.
Ich bin Jerry. >> Sorry?
Es ist in der B-O-R-U-I.
Oh, okay.
Ich sehe dich nicht auf meiner Liste.
Oh, es ist, weil-oh, das macht Sinn.
Haben Sie eine Idee, warum diese while-Schleife möglicherweise nicht wie vorgesehen funktioniert,
Als mit der Bedingung geschrieben?
[Jerry] Du meinst, wie du all das Zeug, nachdem sie in Not the-?
Ja, das ist so, dass man.
Vielleicht müssen wir all diese Sachen in der while-Schleife, die völlig wahr ist gestellt.
Die andere Sache, die ein wenig problematisch ist allerdings, dass diese Bedingung nicht funktioniert.
[Student] Sie benötigen, um es umzudrehen.
Richtig, so ist diese Bedingung nicht immer wahr sein zunächst die Art, wie wir darüber gesprochen.
Wir wollen etwas tun, bis Ende <Anfang,
aber wir wollen etwas Weile zu tun
beginnen ≤ Ende.
>> Es ist das Umkehrung der Logik gibt.
Ich bin schuldig gemacht, diese Fehler die ganze Zeit.
[Student] Warum muss es auf weniger als oder gleich?
Da haben Sie erinnern den Fall, dass wir bekamen
wo es nur ein Element, und wir waren unten,
und wir waren nur die 15 in unser Angebot suchen?
Und unser Anfang und unser Ende waren die gleichen Element.
Wir wollen sicherstellen, dass wir diesen Fall zu behandeln.
Wenn wir das täten eine gerade kleiner,
würden wir nur in der Lage sein, sich auf eine 2-Element-Array.
Einmal bekamen wir bis zu dieser letzten Element, wäre das unser Element, würden wir nie finden.
Hier können wir genau das tun, wie du gesagt hast.
Wir können anfangen Plopp Zeug rechts in der Mitte unserer while-Schleife.
Wir können plop in unserer Mitte.
Wir können all diese nehmen, wenn Aussagen,
ziehen sie aus dieser do-while-Schleife,
plop sie in,
aufräumen ein wenig,
und ich werde weitermachen und speichern Sie diese Revision.
Und an diesem Punkt sind wir schon ziemlich nahe.
Sam.
Ich glaube, Sie haben auch zu haben int Mittelpunkt = Größe - 1/2.
Got it, Größe - 1/2.
Gibt es etwas, was wir brauchen, um über dieser Linie ändern?
Das war ein guter Fang.
>> Was bedeutet Größe zu tun? Werden wir jemals Größe ändern?
Um die Zeile wie diese zu halten, müssen wir die Größe zu ändern.
Wir haben zur Veränderung der Größe jedes Mal, wenn wir um die for-Schleife.
Aber denken Sie daran, wenn wir durch unser Beispiel gehen nur ein bisschen früher,
und wir hatten den Anfang bei 4
und das Ende den ganzen Weg über bei 108?
Wie haben wir berechnen den Mittelpunkt?
Wurden wir mit der Größe?
Oder wir wurden mit Beginn und Ende statt?
Es ist die Differenz zwischen dem Ende und dem Anfang.
Genau, und wie genau soll ich schreiben, dass Charlotte?
Nur am Ende - zu beginnen.
Sie müssten nicht die tun - 1
weil der - 1 hat am Ende aufgenommen werden und der bereits beginnen.
[Nate] Great, bist du völlig Recht.
Wir haben nicht die tun - 1, weil das - 1 aufgenommen hat
und bilanziert, wenn wir zu initialisieren das Ende variabel.
>> Gibt es etwas, was ich brauchen, um syntaktisch zu tun haben diese Linie sinnvoll?
[Schüler] Plus beginnen. >> Plus-beginnen?
[Student] Am Ende.
Weil es nur die Hälfte der Länge berechnet.
Sie müssen den Beginn hinzuzufügen.
[Nate] Was würde das für uns berechnen?
Wenn wir über Ende dieser ersten Iteration der Schleife denken,
Ende wird in der Position index 7 sein.
Beginnen Sie in der Position 0 ist.
Denken Sie daran, wir sind für beide suchen
Position 3 oder Position 4.
Wenn wir an diesem Mathematik aussehen, nur um es ein wenig greifbarer,
legte einige Zahlen hier, wir haben 7, 0,
so 7 - 0, und dann / 2
ist 3 in ganzzahligen Division, das ist.
Dann müssen wir fügen Sie dann wieder unsere beginnen?
Wir wollen nicht in diesem Fall.
Auf der ersten Iteration, wird es in Ordnung sein, weil begin 0 ist.
Aber wie wir Fortschritte machen wir wirklich alles brauchen
end - begin / 2.
Es gibt einen anderen Trick, und das ist nämlich eine der Vorrang.
[Student] Müssen wir Klammern?
[Nate] Genau, und das ist, weil, wenn wir nichts dagegen unternehmen, diese Klammern
dann wird diese Linie statt interpretiert werden
as (Ende) - (Beginn / 2), die wir definitiv nicht wollen.
Achten Sie auf die Vorrangregeln.
[Student] Warum ist es nicht enden + beginnen?
Warum ist es nicht enden + beginnen?
[Student] Warum ist es nicht so, dass?
Warum wäre es + sein?
Ich denke, du hast Recht.
[Student] Weil es durchschnittlich ist?
[Nate] End + beginnen, bist du völlig Recht.
Wow, ich total vermasselt. Sie haben Recht.
Wenn wir taten das Minus, würden wir wollen, um die Rückseite zu beginnen in. hinzuzufügen
In diesem Fall sind Sie sehr richtig, dass wir den Durchschnitt der beiden nehmen wollen,
so wir wollen, um sie hinzuzufügen, im Gegensatz zu ihnen zu subtrahieren.
[Student] Es würde auch funktionieren, wenn Sie am Ende tat - begin / 2 + zu beginnen.
Es wäre, wenn wir-ich glaube so.
>> Zum Beispiel, wenn wir am Beginn der Suche,
und wir verschoben es hier
auf die 15.
Jetzt beginnen die Position 2.
Ende ist an Position 7.
Wenn wir sie subtrahieren, erhalten wir 5.
Kluft, die durch 2, erhalten wir 2.
Und dann fügen wir 2 wieder an,
und dass bringt uns zum vierten Position,
was ist hier genau richtig, das ist der Mittelpunkt.
[Student] Müssen wir kümmern Verpackung nehmen?
In welchem ​​Sinne brauchen wir die Pflege Einwickeln nehmen?
Wenn die Summe oder die Differenz zwischen
je nachdem, wie wir tun, ist es nicht eine gerade Zahl ist.
Dann wird der Computer wird, ob, wenn es 2,5 verwirrt;
Sie nach links oder nach rechts, um zu bestimmen, welche der Mittelpunkt bewegen?
Got it.
Es stellt sich heraus, dass mit Integer-Division,
wir nicht immer bekommen diese Gleitkommazahlen.
Wir nie das Dezimalsystem.
Es ist völlig verworfen.
Wenn Sie einen Computer teilen zwei int-Variablen,
und ein 7 ist, und das andere ist 2,
Sie werden nicht 3,5 als Ergebnis.
Es wird noch 3.
Der Rest werden verworfen, so dass es effektiv Rundung
keine runde, sondern eine Etage, wenn euch vertraut mit, dass in der Mathematik sind,
wo Sie komplett verwerfen dezimal,
und so du Wesentlichen abzuschneiden, auf die nächste
ganze Position, auf die nächste ganze Zahl auf.
[Student] Aber dann ist das problematisch, weil, wenn Sie ein Array von 7 Elemente
dann ist automatisch die dritte Element aus dem Mittelpunkt anstelle der vierten.
Wie gehen wir damit um?
Es ist problematisch, denn wenn wir eine Reihe von 7 hatte,
es würde wählen Sie die dritte Stelle der vierte.
Könnten Sie erklären, ein wenig mehr?
[Student] Denn wenn man 7 Elemente dann das vierte Element
würde der Mittelpunkt sein, richtig?
Angemeldet Ihren Kommentar zu gleich Null indiziert, though.
[Student] Ja, so in Position 3. Das wäre der Mittelpunkt sein.
Yeah.
Oh, okay. Ich sehe, was du meinst.
Es ist irgendwie seltsam, wie wir uns an dieser ganzen Vorstellung verwendet
loszuwerden Dezimalstellen.
Das ist ein großer Punkt.
Wir beenden diese auf.
Wir haben unsere Mittelpunkt berechnet.
>> Wir testen, um zu sehen, ob unsere Nadel ist gleich dem mittleren Wert.
Wir Bedrucken, dass wir es gefunden, aber wirklich, was wollen wir in dieser Situation tun?
Wir haben es gefunden, so dass wir möchten, dass der Anrufer wissen, dass wir es gefunden.
Wir haben eine Funktion, die ein boolean typisierte Funktion ist.
Die Art, wie wir an den Anrufer unserer Funktion, dass wir bereit sind zu gehen
wird man sagen, "Hey, das ist wahr."
Wie würden wir das tun, Kevin?
Sie nicken. >> [Kevin] In return true.
[Nate] Genau, true zurückgeben.
Nun, wenn es nicht gleich, wie würden wir an der linken Hälfte aussehen?
Irgendwelche Ideen?
Stella, irgendwelche Ideen?
Sie müssen eine neue Position für Ende gesetzt.
Yeah.
So haben wir die Position des Mittelpunkts zu tun - das Ende.
Great.
Wir müssen eine neue Position für das Ende gesetzt
auf der linken Hälfte betrachten.
Das war, was wir gesprochen haben, bevor, wo
I keep going back diesem Beispiel.
Ich habe das hier zu beginnen, und dann habe ich am Ende alle den Weg hierher.
>> Auch wenn wir für 15 suchen, und unser Mittelpunkt ist bei 16,
und wir erkennen, "Oops, 16 größer ist.
Wir wollen auf die linke Hälfte zu bewegen. "
Wir würden dann den Ende der 15,
Und das tun wir, indem man sich von der Mitte
und Einstellung, dass als neuer Ende.
Ebenso, wenn wir auf der rechten Hälfte aussehen wollen, wie würden wir das tun?
Haben Sie eine Idee?
[Student] Sie legen beginnen, + 1 Mittelpunkt.
[Nate] Great.
Und jetzt, im Fall, dass wir nichts finden,
bedeutet, dass sich gekümmert für uns?
Daniel, ist, dass Pflege für uns genommen werden?
[Daniel] Nr.
[Nate] Wenn wir es durch das gesamte Array und wir nichts finden,
wo würden, dass gesorgt werden, oder sollten wir kümmern uns darum?
[Daniel] Die while-Bedingung.
[Nate] Ja, die while-Bedingung, genau.
Es kümmert gehen durch das gesamte Array nehmen, wenn wir nichts finden.
Diese while-Schleife wird beendet.
Wir werden nie diesen Zustand erlebt haben,
und wir können false zurück.
Wir können auch verlassen Sie dies, wenn hier wie folgt
denn wenn diese if-Anweisung wahr ist,
und unsere Funktion gibt,
und so werden wir im wesentlichen abort diese Funktion an dieser Stelle
wenn wir wieder wahr.
Aber was passiert mit dieser Struktur hier?
Wird diese vollständig funktionieren, oder gibt es einige logische Fehler drin?
>> Es gibt einige logische Fehler drin, mit der Art, es einzurichten ist.
Was könnte es sein?
[Student] Warum brauchen Sie die - und + 1s?
Das setzt unser Angebot bis zu unserem neuen linken Hälfte und rechte Hälfte sein.
[Student] Aber warum konntest du nicht tun, ohne die - 1s und + 1s?
[Nate] Wir könnten es gleich auf den Mittelpunkt?
Was könnte problematisch sein, darüber?
[Student] Ich denke, es ist ineffizient, weil Sie die Kontrolle einen Wert, das bereits eingecheckte.
[Nate] Genau, so Sam ist völlig richtig.
Wenn Sie das Ende und den Beginn gleich der Mittelpunkt
anstelle von - 1 und + 1 nachdenklich,
an einem gewissen Punkt in der Zukunft werden wir am Ende die Überprüfung der Mitte wieder.
[Student] Ich begann die pset, und dann hatte ich so etwas wie, dass
wo ich vergaß die + 1, und es wurde in einer Endlosschleife.
Richtig, weil man irgendwann wirst nie bekommen beginnen und enden
tatsächlich überlappen.
Cool.
Es ist ein logischer Fehler, und das ist, dass dies auf jeden Fall
ein else if.
Woran kann das liegen?
>> Der Grund dafür ist, wenn es nicht ein else if-hast du es, Kevin zu sehen?
[Kevin] Ja, weil Sie ändern den Endpunkt.
[Nate] Genau.
Wir ändern den Endpunkt,
und wenn es wie diese-wir schriftlich zu machen Leerzeichen zwischen-
es prüft diesen Fall.
Dieser Fall, wenn es gelingt, bricht aus der Funktion.
Dann wird es zu überprüfen diese nächste Fall
und wenn dies gelingt, wird es passen den Endpunkt,
und dann wird es weiter auf und prüfen Sie in diesem Fall.
Aber an diesem Punkt haben wir nicht wollen, dass es auch weiterhin überprüfen.
Glücklicherweise haben wir nicht zurückgesetzt den Mittelpunkt hier
und wir wissen, dass dieser Fall wird nicht gelingen.
Aber wir wollen auf jeden Fall das andere zu stellen, wenn dort
obwohl das könnte in diesem Fall
da wir nicht Anpassung sind der Mittelpunkt, würde das einen Unterschied machen?
Nein, denn diese Fälle sind alle exklusiv.
Auch mein schlechtes.
Wir wissen nicht, denke ich, brauchen diese else if.
Wir können es versuchen, und führen Sie es aus und sehen, was passiert.
Building, ist ein Fehler aufgetreten.
Es ist wahrscheinlich, weil ich diese b-und e die links hier.
Muss ich noch mehr von denen an der Spitze?
Es ist nicht so aussehen.
Wir verkleinern, zu bauen,
dort geht es, so jetzt, wenn wir für 15 suchen,
Ja.
Lassen Sie mich zu vergrößern in.
15, ja. Wir können es wieder laufen.
Hochladen Quellcode, Bau, läuft.
Wir können so etwas wie 13 zu suchen,
und wir haben nichts bekommen Ausdrucken, so dass es nicht zu finden, dass für uns.
Das ist toll, weil es nicht in unserer Liste.
>> Wir sind jetzt die Zeit davon.
Das wird es sein, für diese Woche.
Thanks for joining, und wir sehen uns später.
>> [CS50.TV]