1
00:00:00,000 --> 00:00:02,892
>> [Musik spiller]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Lineær
søgning er en algoritme, vi

4
00:00:07,180 --> 00:00:09,840
kan bruge til at finde et element i et array.

5
00:00:09,840 --> 00:00:11,990
En algoritme tilbagekaldelse
er en trin-for-trin sæt

6
00:00:11,990 --> 00:00:15,030
af instruktioner til at fuldføre en opgave.

7
00:00:15,030 --> 00:00:17,480
>> Den lineære søgning
Algoritmen fungerer således.

8
00:00:17,480 --> 00:00:22,200
Gentage tværs array fra venstre til
ret, på udkig efter en specificeret element.

9
00:00:22,200 --> 00:00:26,380
>> I pseudokode, som er en mere
destilleret udgave af denne sætning,

10
00:00:26,380 --> 00:00:29,840
Hvis det første element er det
du leder efter, kan du stoppe.

11
00:00:29,840 --> 00:00:33,930
Ellers gå videre til næste element, og
holde går igen og igen, indtil du finder

12
00:00:33,930 --> 00:00:36,389
elementet, eller du ikke.

13
00:00:36,389 --> 00:00:38,680
Så vi kan bruge den lineære
søgealgoritme, f.eks

14
00:00:38,680 --> 00:00:42,330
at finde målværdien
ni i dette array.

15
00:00:42,330 --> 00:00:43,870
Nå vi starter ved begyndelsen.

16
00:00:43,870 --> 00:00:45,970
Hvis det er, hvad vi er
leder efter, kan vi stoppe.

17
00:00:45,970 --> 00:00:47,890
Det er ikke, vi er ikke på udkig efter 11.

18
00:00:47,890 --> 00:00:50,220
Så ellers gå til næste element.

19
00:00:50,220 --> 00:00:51,510
>> Så vi ser på 23.

20
00:00:51,510 --> 00:00:52,730
Er 23, hvad vi leder efter?

21
00:00:52,730 --> 00:00:55,614
Nå nej, så vi går videre til den næste
element, og det næste element,

22
00:00:55,614 --> 00:00:57,780
og vi holder gå gennem
denne proces igen og igen

23
00:00:57,780 --> 00:01:01,030
og over, indtil vi lander
på en situation som denne.

24
00:01:01,030 --> 00:01:03,910
>> Ni er, hvad vi leder efter,
og dette element i arrayet

25
00:01:03,910 --> 00:01:05,787
er, er det værdi er ni.

26
00:01:05,787 --> 00:01:08,120
Og så vi fundet, hvad vi er
leder efter, og vi kan stoppe.

27
00:01:08,120 --> 00:01:11,910
Den lineære søgning har
afsluttet med succes.

28
00:01:11,910 --> 00:01:15,370
>> Men hvad hvis vi leder efter
et element, der er ikke i vores array.

29
00:01:15,370 --> 00:01:17,040
Er lineær søgning stadig arbejde?

30
00:01:17,040 --> 00:01:17,540
Godt sikker.

31
00:01:17,540 --> 00:01:19,947
Så vi gentage denne proces
starter ved det første element.

32
00:01:19,947 --> 00:01:21,780
Hvis det er, hvad vi er
leder efter, kan vi stoppe.

33
00:01:21,780 --> 00:01:22,800
Det er det ikke.

34
00:01:22,800 --> 00:01:25,020
Ellers, vi flytter til det næste element.

35
00:01:25,020 --> 00:01:29,050
>> Men vi kan holde gentage denne proces,
undersøge hvert element til gengæld

36
00:01:29,050 --> 00:01:31,720
håber, at vi finder det nummer 50.

37
00:01:31,720 --> 00:01:33,750
Men vi vil ikke vide, om
vi har fundet det nummer 50

38
00:01:33,750 --> 00:01:38,290
eller hvis vi ikke gjorde det, indtil vi har trådt
over hvert enkelt element i arrayet.

39
00:01:38,290 --> 00:01:40,440
>> Først når vi har gjort
det og komme op kort,

40
00:01:40,440 --> 00:01:43,040
kan vi konkludere,
50 er ikke i array'et.

41
00:01:43,040 --> 00:01:46,410
Og så den lineære søgning
algoritme, godt det mislykkedes, per se.

42
00:01:46,410 --> 00:01:49,181
Men ikke i den forstand, at det
lykkedes i at gøre, hvad

43
00:01:49,181 --> 00:01:49,930
spurgte vi det at gøre.

44
00:01:49,930 --> 00:01:52,390
>> Det lykkedes i så
meget, som det ikke fandt 50,

45
00:01:52,390 --> 00:01:54,070
men 50 var ikke i array'et.

46
00:01:54,070 --> 00:01:57,310
Men vi har udtømmende søgt
gennem hver enkelt element

47
00:01:57,310 --> 00:02:00,550
og så, mens vi ikke finde
noget, lineær søgning stadig

48
00:02:00,550 --> 00:02:05,230
lykkes, selv om
element ikke er i array'et.

49
00:02:05,230 --> 00:02:07,507
>> Så hvad er den værste fald
scenarie med lineær søgning?

50
00:02:07,507 --> 00:02:09,590
Nå vi er nødt til at se gennem
hvert enkelt element,

51
00:02:09,590 --> 00:02:14,590
enten fordi måldelen
er det sidste element i arrayet,

52
00:02:14,590 --> 00:02:18,510
eller det element, vi leder efter ikke
faktisk eksisterer i arrayet overhovedet.

53
00:02:18,510 --> 00:02:19,760
Hvad er den bedste tænkelige scenarie?

54
00:02:19,760 --> 00:02:22,430
Godt vi kan finde den
element samme.

55
00:02:22,430 --> 00:02:24,360
Og hvor mange elementer
skal vi så nødt til at se

56
00:02:24,360 --> 00:02:26,859
ved i bedste fald,
hvis vi leder efter det

57
00:02:26,859 --> 00:02:28,400
og vi finder det i starten?

58
00:02:28,400 --> 00:02:29,850
Vi kan stoppe øjeblikkeligt.

59
00:02:29,850 --> 00:02:32,984
>> Hvad siger det om
kompleksiteten af ​​lineær søgning?

60
00:02:32,984 --> 00:02:35,650
Godt i værste fald har vi
at se på hvert enkelt element.

61
00:02:35,650 --> 00:02:38,930
Og så det kører i O i
n, i værste fald.

62
00:02:38,930 --> 00:02:41,540
>> I bedste fald, vi skal
finde elementet med det samme.

63
00:02:41,540 --> 00:02:44,750
Og så kører i omega på 1.

64
00:02:44,750 --> 00:02:45,780
>> Jeg er Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Det er CS50.

66
00:02:48,020 --> 00:02:49,876