Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Linear Suche]
[Patrick Schmid, Harvard University]
[This Is CS50.] [CS50.TV]
Die Suche ist etwas, das Sie wahrscheinlich öfter, als Sie denken.
Offensichtlich jedes Mal, wenn Sie einen Web-Browser
und die Suche nach einer Web-Seite -
oder suchen Sie für Ihre Freunde auf Ihre Lieblings-Social-Networking-Website -
Sie suchen.
Aber das ist nur ein kleiner Teil der Suche, dass Sie tun, auf einer täglichen Basis.
Wenn Sie, dass ein blaues Hemd im Schrank finden wollen,
oder dass perfekte rote Bluse für die Gelegenheit,
Sie durchsuchen.
Wenn Sie ein Geschäft, dass Sie noch nie in zuvor gehen,
und du bist für den Brokkoli in der Gemüseabteilung Mittelgang suchen
Sie durchsuchen.
Was können Sie begann zu bemerken, haben
ist, dass je nachdem, was Sie suchen
oder, wie die Elemente organisiert werden, wenn man nach ihnen suchen
es hat einen Einfluss darauf, wie man zu suchen.
Zum Beispiel, wenn Sie Ihre Hemden werden in den Schrank hängen,
Sie können wahrscheinlich nur abholen ohne viel suchen.
Wenn Sie davon aus, du bist noch zu Fuß den Gang hinunter
um den Brokkoli zu bekommen, haben Sie wahrscheinlich auf allen anderen Gemüsesorten aussehen
bevor Sie feststellen, dass Brokkoli.
Lineare Suche ist ein Beispiel für ein solches Suchverfahren - oder Algorithmus.
Wie der Name andeutet,
durchsucht diese Methode für ein Element in einer linearen Weise, eines nach dem anderen.
Also, wenn Sie sehen die Ergebnisse Ihrer Lieblings-Suchmaschine suchen
und lesen Sie die Liste der Ergebnisse,
Sie verwenden lineare Suche.
Okay. Lassen Sie uns ein Beispiel an.
Sagen wir, wir haben eine Liste von Zahlen - 2, 4, 0, 5, 3, 7, 8 und 1 -
und wir sind für die Zahl 0 suchen.
Natürlich können Sie nur sehen, dass die 0 in der dritten Position ist.
Aber es ist ein Computerprogramm, das nicht glücklich.
Es kann nur "sehen" eine Nummer zu einem Zeitpunkt.
Also, beginnend am Anfang der Liste,
Es "sieht" nur die 2.
Das Programm prüft dann - ist 2 gleich 0?
Offensichtlich nicht. So geht es weiter zur nächsten Zahl, 4.
Hat 4 gleich 0? Nope.
Der nächste, 0. Ah! Null ist gleich 0 ist.
Da haben wir es! Es ist in der dritten Position.
Okay. Lassen Sie uns einige Pseudocode aussehen.
Es ist nur ein paar Zeilen lang, aber wir es betrachten eine Zeile zu einem Zeitpunkt.
Zunächst definieren wir die Funktion - und wir werden es nennen lineare Suche -
und es dauert zwei Argumente - Schlüssel und Array.
Der Schlüssel ist, dass Wert, den wir suchen,
so im vorhergehenden Beispiel war das die Null.
Ein Array ist eine Liste von Nummern
das hat all die Werte, die wir gehen zu suchen.
Also, was wir tun wollen, ist, dass wir wollen, zu betrachten -
aus allen Positionen, also beginnend am Anfang des Arrays
til ganz am Ende des Feldes - so die Länge des Arrays -
Blick auf jede einzelne Position und überprüfen Sie jeden ein.
Also das ist, was dieses "for"-Schleife tut.
Und an jeder Position, wir gehen zu sagen,
"Ist dieser Wert zu diesem aktuellen Position gleich dem Schlüssel, den wir suchen?"
So - im vorhergehenden Beispiel war wiederum Schlüssel 0 -
so sagen wir: "Ist das Array an Position i auf Null gleich?"
Wenn ja, werden wir 'i' zurückzukehren, denn das ist die aktuelle Position, die wir gerade sind.
Also, in dem vorherigen Beispiel,
Das war die dritte Position.
Wenn wir durch das gesamte Array verschwunden
und wir haben nichts gefunden -
so sagen wir, wir wurden für die Nummer 500 suchen
dem war eindeutig nicht in diesem Beispiel -
Wir müssen etwas zurückgeben,
und wir gehen auf -1 zurück.
Und wir gerade wieder -1, denn das ist eine Position,
das heißt nicht in der Anordnung vorhanden sind.
Und damit heißt, wenn Sie es wieder aus einer Funktion
er sagt: "Hmm, okay. Ich glaube, ich habe nichts gefunden.
So, dass 500 noch nie dort war. "
Die nette Sache über lineare Suche ist, dass
es wird auf keiner Liste von Elementen arbeiten,
unabhängig davon, wie die Elemente geordnet sind.
Es spielt keine Rolle, wo der Brokkoli ist in der Gemüseabteilung Gang.
Solange Sie zu Fuß den Gang von Anfang bis zum Ende,
Sie sind verpflichtet, es zu finden,
vorausgesetzt, das Geschäft ist nicht aus der Broccoli laufen, natürlich.
Aber es ist größte Stärke ist auch seine größte Schwäche.
Angenommen, Sie haben eine Liste von 200-Nummern
, die von 1 bis 200 sortiert.
Wenn Sie die Nummer 198 suchen,
Sie haben fast die gesamte Liste von Zahlen suchen
bevor Sie die, die Sie suchen.
Es muss einen besseren Weg geben!
Seien Sie versichert, es gibt.
Aber das ist ein Thema für einen anderen Video.
Auch ärgern Sie sich nicht!
Nur weil lineare Suche ist nicht die beste Lösung in allen Situationen,
es bedeutet nicht, dass es nicht in handliches kommen.
Ansonsten, wie würden Sie feststellen, dass Brokkoli in der Gemüseabteilung Gang?
Mein Name ist Patrick Schmid, und dies ist CS50.
[CS50.TV]