1
00:00:00,000 --> 00:00:02,892
>> [Muziek]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
search is een algoritme dat we

4
00:00:07,180 --> 00:00:09,840
kunnen gebruiken om een ​​element in een array zijn.

5
00:00:09,840 --> 00:00:11,990
Een algoritme recall
is een set van stap-voor-stap

6
00:00:11,990 --> 00:00:15,030
instructies voor het uitvoeren van een taak.

7
00:00:15,030 --> 00:00:17,480
>> De lineaire zoekopdracht
algoritme werkt als volgt.

8
00:00:17,480 --> 00:00:22,200
Herhalen tegenover de array van links naar
rechts, op zoek naar een bepaald element.

9
00:00:22,200 --> 00:00:26,380
>> In pseudocode, die een
gedistilleerd versie van deze zin,

10
00:00:26,380 --> 00:00:29,840
wanneer het eerste element is wat
u zoekt, kunt u stoppen.

11
00:00:29,840 --> 00:00:33,930
Anders naar het volgende element en
houden over en over te gaan tot u

12
00:00:33,930 --> 00:00:36,389
het element, of je doet het niet.

13
00:00:36,389 --> 00:00:38,680
Dus we kunnen de lineaire gebruiken
zoekalgoritme bijvoorbeeld

14
00:00:38,680 --> 00:00:42,330
aan de streefwaarde te vinden
negen in deze array.

15
00:00:42,330 --> 00:00:43,870
Nou we beginnen bij het begin.

16
00:00:43,870 --> 00:00:45,970
Als het is wat we zijn
zoekt, kunnen we stoppen.

17
00:00:45,970 --> 00:00:47,890
Het is niet, we zijn niet op zoek naar 11.

18
00:00:47,890 --> 00:00:50,220
Dus anders naar het volgende element.

19
00:00:50,220 --> 00:00:51,510
>> Dus we kijken naar 23.

20
00:00:51,510 --> 00:00:52,730
23 is wat we zoeken?

21
00:00:52,730 --> 00:00:55,614
Nou nee, dus we gaan naar de volgende
element en het volgende element,

22
00:00:55,614 --> 00:00:57,780
en we blijven gaan door
dit proces over en voorbij

23
00:00:57,780 --> 00:01:01,030
en over, totdat we landen
op een situatie als deze.

24
00:01:01,030 --> 00:01:03,910
>> Negen is wat we zoeken,
en dit element van de array

25
00:01:03,910 --> 00:01:05,787
is, is de waarde van negen.

26
00:01:05,787 --> 00:01:08,120
En dus we vonden wat we
zoekt, en we kunnen stoppen.

27
00:01:08,120 --> 00:01:11,910
De lineaire zoekopdracht heeft
afgerond, met succes.

28
00:01:11,910 --> 00:01:15,370
>> Maar hoe zit het als we op zoek bent naar
een element dat niet in ons aanbod.

29
00:01:15,370 --> 00:01:17,040
Heeft lineair zoeken nog steeds werken?

30
00:01:17,040 --> 00:01:17,540
Nou zeker.

31
00:01:17,540 --> 00:01:19,947
Dus we dit proces herhalen
vanaf het eerste element.

32
00:01:19,947 --> 00:01:21,780
Als het is wat we zijn
zoekt, kunnen we stoppen.

33
00:01:21,780 --> 00:01:22,800
Het is niet.

34
00:01:22,800 --> 00:01:25,020
Anders gaan we naar het volgende element.

35
00:01:25,020 --> 00:01:29,050
>> Maar we kunnen blijven herhalen dit proces,
onderzoekt elk element op zijn beurt,

36
00:01:29,050 --> 00:01:31,720
in de hoop dat we de nummer 50.

37
00:01:31,720 --> 00:01:33,750
Maar we zullen niet weten of
we hebben het nummer 50 gevonden

38
00:01:33,750 --> 00:01:38,290
of als we dat niet deden, totdat we hebben gestapt
dan elk element van de array.

39
00:01:38,290 --> 00:01:40,440
>> Alleen als we hebben gedaan
dat en komen kort,

40
00:01:40,440 --> 00:01:43,040
kunnen we concluderen dat
50 niet in de array.

41
00:01:43,040 --> 00:01:46,410
En zo het lineair zoeken
algoritme, goed het niet per se.

42
00:01:46,410 --> 00:01:49,181
Maar niet in de zin dat het
was niet succesvol in het doen wat

43
00:01:49,181 --> 00:01:49,930
vroegen we om te doen.

44
00:01:49,930 --> 00:01:52,390
>> Het was niet succesvol in als
veel als het niet vinden 50,

45
00:01:52,390 --> 00:01:54,070
maar 50 was niet in de array.

46
00:01:54,070 --> 00:01:57,310
Maar we hebben uitvoerig gezocht
door middel van elk element

47
00:01:57,310 --> 00:02:00,550
en zo, terwijl we niet vinden
iets, lineair zoeken nog steeds

48
00:02:00,550 --> 00:02:05,230
slaagt zelfs indien de
element niet in de array.

49
00:02:05,230 --> 00:02:07,507
>> Dus wat is het ergste geval
scenario met lineair zoeken?

50
00:02:07,507 --> 00:02:09,590
Nou moeten we kijken door
elk element,

51
00:02:09,590 --> 00:02:14,590
hetzij omdat het doelelement
is het laatste element van de array,

52
00:02:14,590 --> 00:02:18,510
of het element we zoeken niet
werkelijk bestaan ​​in de matrix helemaal.

53
00:02:18,510 --> 00:02:19,760
Wat is de beste case scenario?

54
00:02:19,760 --> 00:02:22,430
Goed we kunnen vinden van de
element onmiddellijk.

55
00:02:22,430 --> 00:02:24,360
En hoeveel elementen
moeten we dan kijken

56
00:02:24,360 --> 00:02:26,859
op de in het gunstigste geval,
als we naar op zoek

57
00:02:26,859 --> 00:02:28,400
en we vinden het in het begin?

58
00:02:28,400 --> 00:02:29,850
We kunnen onmiddellijk stoppen.

59
00:02:29,850 --> 00:02:32,984
>> Wat zegt dit over de
complexiteit van lineair zoeken?

60
00:02:32,984 --> 00:02:35,650
Welnu, in het ergste geval, we hebben
om te kijken naar elk element.

61
00:02:35,650 --> 00:02:38,930
En zo draait in O van
n, in het ergste geval.

62
00:02:38,930 --> 00:02:41,540
>> In het beste geval, we gaan
vind het element onmiddellijk.

63
00:02:41,540 --> 00:02:44,750
En zo loopt aan omega van 1.

64
00:02:44,750 --> 00:02:45,780
>> Ik ben Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Dit is CS50.

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