1
00:00:00,000 --> 00:00:02,892
>> [Speel van musiek]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Lineêre
soek is 'n algoritme ons

4
00:00:07,180 --> 00:00:09,840
kan gebruik om 'n element in 'n skikking te vind.

5
00:00:09,840 --> 00:00:11,990
'N algoritme herroep
is 'n stel stap-vir-stap

6
00:00:11,990 --> 00:00:15,030
instruksies vir die voltooiing van 'n taak.

7
00:00:15,030 --> 00:00:17,480
>> Die lineêre soek
algoritme werk soos volg.

8
00:00:17,480 --> 00:00:22,200
Itereer oor die skikking van links na
reg, op soek na 'n gespesifiseerde element.

9
00:00:22,200 --> 00:00:26,380
>> In pseudokode, wat 'n meer
gedistilleerde weergawe van hierdie sin,

10
00:00:26,380 --> 00:00:29,840
As die eerste element is wat
jy soek, kan jy stop.

11
00:00:29,840 --> 00:00:33,930
Anders, skuif na die volgende element en
hou oor en oor gaan totdat jy

12
00:00:33,930 --> 00:00:36,389
die element, of jy doen nie.

13
00:00:36,389 --> 00:00:38,680
So kan ons die lineêre gebruik
soek algoritme, byvoorbeeld,

14
00:00:38,680 --> 00:00:42,330
om die teiken waarde vind
nege in hierdie reeks.

15
00:00:42,330 --> 00:00:43,870
Wel ons begin by die begin.

16
00:00:43,870 --> 00:00:45,970
As dit is wat ons is
soek, kan ons stop.

17
00:00:45,970 --> 00:00:47,890
Dit is nie, ons is nie op soek na 11.

18
00:00:47,890 --> 00:00:50,220
So anders, skuif na die volgende element.

19
00:00:50,220 --> 00:00:51,510
>> So ons kyk na 23.

20
00:00:51,510 --> 00:00:52,730
Is 23 wat ons soek?

21
00:00:52,730 --> 00:00:55,614
Wel nee, sodat ons beweeg op na die volgende
element, en die volgende element,

22
00:00:55,614 --> 00:00:57,780
en ons hou gaan deur
hierdie proses oor en oor

23
00:00:57,780 --> 00:01:01,030
en oor, totdat ons land
op 'n situasie soos hierdie.

24
00:01:01,030 --> 00:01:03,910
>> Nege is wat ons soek,
en hierdie element van die skikking

25
00:01:03,910 --> 00:01:05,787
is, is dit se waarde is nege.

26
00:01:05,787 --> 00:01:08,120
En so het ons gevind wat ons
soek, en ons kan stop.

27
00:01:08,120 --> 00:01:11,910
Die lineêre soek het
voltooi, suksesvol.

28
00:01:11,910 --> 00:01:15,370
>> Maar wat van as ons is op soek na
'n element wat nie in ons verskeidenheid.

29
00:01:15,370 --> 00:01:17,040
Maak lineêre soek nog werk?

30
00:01:17,040 --> 00:01:17,540
Wel seker.

31
00:01:17,540 --> 00:01:19,947
Sodat ons hierdie proses herhaal
begin by die eerste element.

32
00:01:19,947 --> 00:01:21,780
As dit is wat ons is
soek, kan ons stop.

33
00:01:21,780 --> 00:01:22,800
Dit is nie.

34
00:01:22,800 --> 00:01:25,020
Anders, beweeg ons na die volgende element.

35
00:01:25,020 --> 00:01:29,050
>> Maar ons kan hou herhaal hierdie proses,
ondersoek elke element in sy beurt,

36
00:01:29,050 --> 00:01:31,720
hoop dat ons die nommer 50.

37
00:01:31,720 --> 00:01:33,750
Maar ons sal nie weet as
ons het die nommer 50 gevind

38
00:01:33,750 --> 00:01:38,290
of as ons het nie, totdat ons het uitgetree
oor elke enkele element van die skikking.

39
00:01:38,290 --> 00:01:40,440
>> Slegs een keer wat ons gedoen het
wat en kom kort,

40
00:01:40,440 --> 00:01:43,040
kan ons aflei dat
50 is nie in die skikking.

41
00:01:43,040 --> 00:01:46,410
En so het die lineêre soek
algoritme, goed dit misluk, per se.

42
00:01:46,410 --> 00:01:49,181
Maar nie in die sin dat dit
was onsuksesvol in te doen wat

43
00:01:49,181 --> 00:01:49,930
ons gevra om dit te doen.

44
00:01:49,930 --> 00:01:52,390
>> Dit was onsuksesvol in as
veel as dit nie vind 50,

45
00:01:52,390 --> 00:01:54,070
maar 50 was nie in die skikking.

46
00:01:54,070 --> 00:01:57,310
Maar ons het uitvoerig gesoek
deur elke enkele element

47
00:01:57,310 --> 00:02:00,550
en so, terwyl ons nie vind
enigiets, lineêre soek steeds

48
00:02:00,550 --> 00:02:05,230
slaag selfs al is die
element is nie in die skikking.

49
00:02:05,230 --> 00:02:07,507
>> So, wat is die ergste geval
scenario met lineêre soek?

50
00:02:07,507 --> 00:02:09,590
Wel, ons het om te kyk deur
elke enkele element,

51
00:02:09,590 --> 00:02:14,590
óf omdat die teiken element
is die laaste element van die skikking,

52
00:02:14,590 --> 00:02:18,510
of die element wat ons soek nie
werklik bestaan ​​in die skikking nie.

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

54
00:02:19,760 --> 00:02:22,430
Wel, ons kan vind die
element onmiddellik.

55
00:02:22,430 --> 00:02:24,360
En hoeveel elemente
het ons dan om te kyk

56
00:02:24,360 --> 00:02:26,859
op in die beste geval,
As ons kyk na dit

57
00:02:26,859 --> 00:02:28,400
en ons vind dit heel aan die begin?

58
00:02:28,400 --> 00:02:29,850
Ons kan onmiddellik stop.

59
00:02:29,850 --> 00:02:32,984
>> Wat sê dit oor die
kompleksiteit van lineêre soek?

60
00:02:32,984 --> 00:02:35,650
Wel, in die ergste geval, ons het
om te kyk na elke enkele element.

61
00:02:35,650 --> 00:02:38,930
En so het dit loop in O van
n, in die ergste geval.

62
00:02:38,930 --> 00:02:41,540
>> In die beste geval, ons gaan
vind die element onmiddellik.

63
00:02:41,540 --> 00:02:44,750
En so loop in omega van 1.

64
00:02:44,750 --> 00:02:45,780
>> Ek is Doug Lloyd.

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

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