[Musikwiedergabe] DOUG LLOYD: Linear Suche ist ein Algorithmus, wir verwenden können, um ein Element in einem Array zu finden. Ein Algorithmus Rückruf ist ein Schritt-für-Schritt-Set von Anweisungen zur Durchführung einer Aufgabe. 

Die lineare Suche Algorithmus arbeitet wie folgt. Führen Sie eine Iteration über das Array von links nach rechts, auf der Suche nach einem bestimmten Element. 

In Pseudocode, dem eine weitere destilliertem Version dieses Satzes, wenn das erste Element ist, was Sie suchen, können Sie aufhören zu suchen. Andernfalls mit dem nächsten Element bewegen und fahren Sie immer und immer wieder, bis Sie das Element, oder eben nicht. So können wir die lineare verwenden Such-Algorithmus, beispielsweise den Zielwert zu finden neun in diesem Array. Nun beginnen wir am Anfang. Wenn es ist, was wir sind auf der Suche nach, können wir stoppen. Es ist nicht, wir suchen nicht 11. So anders, zu bewegen, um das nächste Element. 

Also schauen wir auf 23. Ist 23, was wir suchen? Also nein, so bewegen wir uns auf die nächste Element und das nächste Element, und wir halten Sie durch dieser Prozess immer und immer wieder, bis wir landen Auf einer Situation wie dieser. 

Nine ist das, was wir suchen, und das Element der Gruppe ist, ist es den Wert neun. Und so fanden wir, was wir sind auf der Suche nach, und wir stoppen. Die lineare Suche hat abgeschlossen ist, erfolgreich. 

Aber was ist, wenn wir suchen ein Element, das in unser Angebot nicht ist. Hat lineare Suche noch? Na sicher. Also haben wir diesen Vorgang wiederholen beginnend mit dem ersten Element. Wenn es ist, was wir sind auf der Suche nach, können wir stoppen. Ist es nicht. Ansonsten bewegen wir uns auf das nächste Element. 

Aber wir können immer wiederholen Sie diesen Vorgang, Untersuchen jedes Element wiederum in der Hoffnung, dass wir die Zahl 50. Aber wir werden nicht wissen, ob wir haben die Nummer 50 gefunden oder, wenn wir nicht, bis wir getreten habe auf jedem einzelnen Element des Arrays. 

Erst wenn wir getan haben dass und zu kurz kommt, können wir schließen, dass 50 nicht in der Anordnung. Und so ist die lineare Suche Algorithmus, gut es konnte, an sich. Aber nicht in dem Sinne, dass es war nicht erfolgreich zu tun, was fragten wir, es zu tun. 

Es war nicht erfolgreich, wie viel, wie es nicht das finden 50, aber 50 nicht in der Anordnung. Aber wir haben ausgiebig gesucht durch jedes einzelne Element und so, während wir nicht gefunden alles, lineare Suche noch gelingt es, selbst wenn das Element nicht in der Anordnung. 

Also, was ist der schlimmste Fall Szenario mit linearen Suche? Nun müssen wir schauen durch jedes einzelne Element, entweder weil das Zielelement das letzte Element des Arrays, oder das Element, die wir suchen nicht tatsächlich in der Anordnung existieren. Was ist der beste-Case-Szenario? Nun, wir könnten das zu finden Element sofort. Und wie viele Elemente wir müssen dann schauen an im besten Fall, wenn wir danach suchen und wir finden es ganz am Anfang? Wir können sofort zu stoppen. 

Was sagt das über das sagen, Komplexität der linearen Suche? Auch im schlimmsten Fall haben wir bei jedem einzelnen Element zu suchen. Und so ist es in der O läuft n, im schlimmsten Fall. 

Im besten Fall, wir werden finden Sie das Element sofort. Und so läuft an Omega von 1. 

Ich bin Doug Lloyd. Dies ist CS50.