1 00:00:00,000 --> 00:00:02,892 >> [Musikwiedergabe] 2 00:00:02,892 --> 00:00:05,347 3 00:00:05,347 --> 00:00:07,180 DOUG LLOYD: Linear Suche ist ein Algorithmus, wir 4 00:00:07,180 --> 00:00:09,840 verwenden können, um ein Element in einem Array zu finden. 5 00:00:09,840 --> 00:00:11,990 Ein Algorithmus Rückruf ist ein Schritt-für-Schritt-Set 6 00:00:11,990 --> 00:00:15,030 von Anweisungen zur Durchführung einer Aufgabe. 7 00:00:15,030 --> 00:00:17,480 >> Die lineare Suche Algorithmus arbeitet wie folgt. 8 00:00:17,480 --> 00:00:22,200 Führen Sie eine Iteration über das Array von links nach rechts, auf der Suche nach einem bestimmten Element. 9 00:00:22,200 --> 00:00:26,380 >> In Pseudocode, dem eine weitere destilliertem Version dieses Satzes, 10 00:00:26,380 --> 00:00:29,840 wenn das erste Element ist, was Sie suchen, können Sie aufhören zu suchen. 11 00:00:29,840 --> 00:00:33,930 Andernfalls mit dem nächsten Element bewegen und fahren Sie immer und immer wieder, bis Sie 12 00:00:33,930 --> 00:00:36,389 das Element, oder eben nicht. 13 00:00:36,389 --> 00:00:38,680 So können wir die lineare verwenden Such-Algorithmus, beispielsweise 14 00:00:38,680 --> 00:00:42,330 den Zielwert zu finden neun in diesem Array. 15 00:00:42,330 --> 00:00:43,870 Nun beginnen wir am Anfang. 16 00:00:43,870 --> 00:00:45,970 Wenn es ist, was wir sind auf der Suche nach, können wir stoppen. 17 00:00:45,970 --> 00:00:47,890 Es ist nicht, wir suchen nicht 11. 18 00:00:47,890 --> 00:00:50,220 So anders, zu bewegen, um das nächste Element. 19 00:00:50,220 --> 00:00:51,510 >> Also schauen wir auf 23. 20 00:00:51,510 --> 00:00:52,730 Ist 23, was wir suchen? 21 00:00:52,730 --> 00:00:55,614 Also nein, so bewegen wir uns auf die nächste Element und das nächste Element, 22 00:00:55,614 --> 00:00:57,780 und wir halten Sie durch dieser Prozess immer 23 00:00:57,780 --> 00:01:01,030 und immer wieder, bis wir landen Auf einer Situation wie dieser. 24 00:01:01,030 --> 00:01:03,910 >> Nine ist das, was wir suchen, und das Element der Gruppe 25 00:01:03,910 --> 00:01:05,787 ist, ist es den Wert neun. 26 00:01:05,787 --> 00:01:08,120 Und so fanden wir, was wir sind auf der Suche nach, und wir stoppen. 27 00:01:08,120 --> 00:01:11,910 Die lineare Suche hat abgeschlossen ist, erfolgreich. 28 00:01:11,910 --> 00:01:15,370 >> Aber was ist, wenn wir suchen ein Element, das in unser Angebot nicht ist. 29 00:01:15,370 --> 00:01:17,040 Hat lineare Suche noch? 30 00:01:17,040 --> 00:01:17,540 Na sicher. 31 00:01:17,540 --> 00:01:19,947 Also haben wir diesen Vorgang wiederholen beginnend mit dem ersten Element. 32 00:01:19,947 --> 00:01:21,780 Wenn es ist, was wir sind auf der Suche nach, können wir stoppen. 33 00:01:21,780 --> 00:01:22,800 Ist es nicht. 34 00:01:22,800 --> 00:01:25,020 Ansonsten bewegen wir uns auf das nächste Element. 35 00:01:25,020 --> 00:01:29,050 >> Aber wir können immer wiederholen Sie diesen Vorgang, Untersuchen jedes Element wiederum 36 00:01:29,050 --> 00:01:31,720 in der Hoffnung, dass wir die Zahl 50. 37 00:01:31,720 --> 00:01:33,750 Aber wir werden nicht wissen, ob wir haben die Nummer 50 gefunden 38 00:01:33,750 --> 00:01:38,290 oder, wenn wir nicht, bis wir getreten habe auf jedem einzelnen Element des Arrays. 39 00:01:38,290 --> 00:01:40,440 >> Erst wenn wir getan haben dass und zu kurz kommt, 40 00:01:40,440 --> 00:01:43,040 können wir schließen, dass 50 nicht in der Anordnung. 41 00:01:43,040 --> 00:01:46,410 Und so ist die lineare Suche Algorithmus, gut es konnte, an sich. 42 00:01:46,410 --> 00:01:49,181 Aber nicht in dem Sinne, dass es war nicht erfolgreich zu tun, was 43 00:01:49,181 --> 00:01:49,930 fragten wir, es zu tun. 44 00:01:49,930 --> 00:01:52,390 >> Es war nicht erfolgreich, wie viel, wie es nicht das finden 50, 45 00:01:52,390 --> 00:01:54,070 aber 50 nicht in der Anordnung. 46 00:01:54,070 --> 00:01:57,310 Aber wir haben ausgiebig gesucht durch jedes einzelne Element 47 00:01:57,310 --> 00:02:00,550 und so, während wir nicht gefunden alles, lineare Suche noch 48 00:02:00,550 --> 00:02:05,230 gelingt es, selbst wenn das Element nicht in der Anordnung. 49 00:02:05,230 --> 00:02:07,507 >> Also, was ist der schlimmste Fall Szenario mit linearen Suche? 50 00:02:07,507 --> 00:02:09,590 Nun müssen wir schauen durch jedes einzelne Element, 51 00:02:09,590 --> 00:02:14,590 entweder weil das Zielelement das letzte Element des Arrays, 52 00:02:14,590 --> 00:02:18,510 oder das Element, die wir suchen nicht tatsächlich in der Anordnung existieren. 53 00:02:18,510 --> 00:02:19,760 Was ist der beste-Case-Szenario? 54 00:02:19,760 --> 00:02:22,430 Nun, wir könnten das zu finden Element sofort. 55 00:02:22,430 --> 00:02:24,360 Und wie viele Elemente wir müssen dann schauen 56 00:02:24,360 --> 00:02:26,859 an im besten Fall, wenn wir danach suchen 57 00:02:26,859 --> 00:02:28,400 und wir finden es ganz am Anfang? 58 00:02:28,400 --> 00:02:29,850 Wir können sofort zu stoppen. 59 00:02:29,850 --> 00:02:32,984 >> Was sagt das über das sagen, Komplexität der linearen Suche? 60 00:02:32,984 --> 00:02:35,650 Auch im schlimmsten Fall haben wir bei jedem einzelnen Element zu suchen. 61 00:02:35,650 --> 00:02:38,930 Und so ist es in der O läuft n, im schlimmsten Fall. 62 00:02:38,930 --> 00:02:41,540 >> Im besten Fall, wir werden finden Sie das Element sofort. 63 00:02:41,540 --> 00:02:44,750 Und so läuft an Omega von 1. 64 00:02:44,750 --> 00:02:45,780 >> Ich bin Doug Lloyd. 65 00:02:45,780 --> 00:02:48,020 Dies ist CS50. 66 00:02:48,020 --> 00:02:49,876