1 00:00:00,000 --> 00:00:02,892 >> [MUSIK SPELA] 2 00:00:02,892 --> 00:00:05,347 3 00:00:05,347 --> 00:00:07,180 DOUG LLOYD: Linjär sökning är en algoritm som vi 4 00:00:07,180 --> 00:00:09,840 kan använda för att hitta ett element i en array. 5 00:00:09,840 --> 00:00:11,990 En algoritm återkallande är ett steg-för-steg set 6 00:00:11,990 --> 00:00:15,030 instruktioner för att fylla en uppgift. 7 00:00:15,030 --> 00:00:17,480 >> Den linjära sökning Algoritmen fungerar enligt följande. 8 00:00:17,480 --> 00:00:22,200 Iterera över uppsättningen från vänster till höger, letar efter en viss del. 9 00:00:22,200 --> 00:00:26,380 >> I pseudokod, som är ett mer destillerad version av denna mening, 10 00:00:26,380 --> 00:00:29,840 om det första elementet är vad du letar efter, kan du sluta. 11 00:00:29,840 --> 00:00:33,930 Annars flyttar till nästa element och fortsätt om och om igen tills du hittar 12 00:00:33,930 --> 00:00:36,389 elementet, eller du inte. 13 00:00:36,389 --> 00:00:38,680 Så vi kan använda det linjära sökalgoritm, till exempel, 14 00:00:38,680 --> 00:00:42,330 att hitta målvärdet nio i denna samling. 15 00:00:42,330 --> 00:00:43,870 Jo vi börjar från början. 16 00:00:43,870 --> 00:00:45,970 Om det är vad vi är söker, kan vi sluta. 17 00:00:45,970 --> 00:00:47,890 Det är inte, vi är inte ute efter 11. 18 00:00:47,890 --> 00:00:50,220 Så annars, gå till nästa element. 19 00:00:50,220 --> 00:00:51,510 >> Så vi tittar på 23. 20 00:00:51,510 --> 00:00:52,730 Är 23 det vi letar efter? 21 00:00:52,730 --> 00:00:55,614 Jo nej, så vi går vidare till nästa elementet, och nästa element, 22 00:00:55,614 --> 00:00:57,780 och vi håller gå igenom denna process om och om igen 23 00:00:57,780 --> 00:01:01,030 och över, tills vi landar på en situation som denna. 24 00:01:01,030 --> 00:01:03,910 >> Nio är vad vi letar efter, och denna del av gruppen 25 00:01:03,910 --> 00:01:05,787 är, är det värde nio. 26 00:01:05,787 --> 00:01:08,120 Och så fann vi vad vi är letar efter, och vi kan sluta. 27 00:01:08,120 --> 00:01:11,910 Den linjära sökningen har klar, framgångsrikt. 28 00:01:11,910 --> 00:01:15,370 >> Men vad händer om vi letar efter ett element som inte är i vårt utbud. 29 00:01:15,370 --> 00:01:17,040 Har linjär sökning fortfarande fungerar? 30 00:01:17,040 --> 00:01:17,540 Väl säker. 31 00:01:17,540 --> 00:01:19,947 Så vi upprepa denna process med början vid det första elementet. 32 00:01:19,947 --> 00:01:21,780 Om det är vad vi är söker, kan vi sluta. 33 00:01:21,780 --> 00:01:22,800 Det är inte. 34 00:01:22,800 --> 00:01:25,020 Annars, vi flyttar till nästa element. 35 00:01:25,020 --> 00:01:29,050 >> Men vi kan fortsätta att upprepa denna process, undersöka varje element i sin tur 36 00:01:29,050 --> 00:01:31,720 hoppas att vi hittar numret 50. 37 00:01:31,720 --> 00:01:33,750 Men vi kommer inte att veta om vi har hittat numret 50 38 00:01:33,750 --> 00:01:38,290 eller om vi inte förrän vi har klivit över varje enskilt element i matrisen. 39 00:01:38,290 --> 00:01:40,440 >> Först när vi har gjort det och komma upp kort, 40 00:01:40,440 --> 00:01:43,040 kan vi konstatera att 50 är inte i arrayen. 41 00:01:43,040 --> 00:01:46,410 Och så den linjära sökningen algoritm, ja det inte i sig. 42 00:01:46,410 --> 00:01:49,181 Men inte i den meningen att den lyckades inte göra det 43 00:01:49,181 --> 00:01:49,930 vi bett den att göra. 44 00:01:49,930 --> 00:01:52,390 >> Det lyckades inte så mycket som det inte hittade 50, 45 00:01:52,390 --> 00:01:54,070 men 50 var inte i arrayen. 46 00:01:54,070 --> 00:01:57,310 Men vi har uttömmande sökt genom varje enskilt element 47 00:01:57,310 --> 00:02:00,550 och så, medan vi hittade inte något, linjär sökning fortfarande 48 00:02:00,550 --> 00:02:05,230 lyckas även om elementet är inte i arrayen. 49 00:02:05,230 --> 00:02:07,507 >> Så vad är det värsta fallet scenario med linjär sökning? 50 00:02:07,507 --> 00:02:09,590 Jo vi måste titta igenom varje enskilt element, 51 00:02:09,590 --> 00:02:14,590 antingen för att målelementet är det sista elementet i arrayen, 52 00:02:14,590 --> 00:02:18,510 eller elementet vi söker inte faktiskt finns i arrayen huvudtaget. 53 00:02:18,510 --> 00:02:19,760 Vad är det bästa scenariot? 54 00:02:19,760 --> 00:02:22,430 Jo vi kan hitta den elementet omedelbart. 55 00:02:22,430 --> 00:02:24,360 Och hur många element har måste vi se 56 00:02:24,360 --> 00:02:26,859 på i bästa fall, Om vi ​​letar efter det 57 00:02:26,859 --> 00:02:28,400 och vi tycker att det i början? 58 00:02:28,400 --> 00:02:29,850 Vi kan sluta omedelbart. 59 00:02:29,850 --> 00:02:32,984 >> Vad säger detta om komplexitet linjär sökning? 60 00:02:32,984 --> 00:02:35,650 Väl i värsta fall, vi har att titta på varje enskilt element. 61 00:02:35,650 --> 00:02:38,930 Och så det körs i O n, i värsta fall. 62 00:02:38,930 --> 00:02:41,540 >> I bästa fall, vi ska hitta elementet omedelbart. 63 00:02:41,540 --> 00:02:44,750 Och så körs i omega 1. 64 00:02:44,750 --> 00:02:45,780 >> Jag är Doug Lloyd. 65 00:02:45,780 --> 00:02:48,020 Detta är CS50. 66 00:02:48,020 --> 00:02:49,876