1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [Linear Otsing]

2
00:00:02,430 --> 00:00:04,430
[Patrick Schmid, Harvard University]

3
00:00:04,430 --> 00:00:07,430
[See on CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
Otsimine on midagi, mida sa ilmselt teha sagedamini kui te arvate.

5
00:00:09,440 --> 00:00:11,600
Ilmselt iga kord, kui avada veebibrauseris

6
00:00:11,600 --> 00:00:12,890
ja otsida veebilehe -

7
00:00:12,890 --> 00:00:15,620
või otsi oma sõpru oma lemmik suhtlusvõrgustik -

8
00:00:15,620 --> 00:00:16,610
otsite.

9
00:00:16,610 --> 00:00:19,690
Aga see on ainult väike osa otsimine, mida te teete iga päev.

10
00:00:19,690 --> 00:00:21,720
Kui soovite leida, et üks sinine särk kapis,

11
00:00:21,720 --> 00:00:23,620
või et ideaalne punane pluus jaoks sündmus,

12
00:00:23,620 --> 00:00:24,730
mida te otsite.

13
00:00:24,730 --> 00:00:26,640
Kui te lähete poodi, et te pole kunagi olnud enne,

14
00:00:26,640 --> 00:00:28,590
ja otsite brokkoliga toota vahekäiku

15
00:00:28,590 --> 00:00:29,650
mida te otsite.

16
00:00:29,650 --> 00:00:31,050
Mida olete hakanud märkama

17
00:00:31,050 --> 00:00:32,820
on see, et sõltuvalt sellest, mida sa otsid

18
00:00:32,820 --> 00:00:35,340
või kuidas esemed on korraldatud kui otsite neid

19
00:00:35,340 --> 00:00:37,670
see mõjutab, kuidas otsida.

20
00:00:37,670 --> 00:00:40,990
Näiteks, kui teie särgid ripuvad kapis,

21
00:00:40,990 --> 00:00:42,840
saab ilmselt lihtsalt korja see välja ilma palju otsida.

22
00:00:42,840 --> 00:00:45,300
Kui sa eeldades, et teil on kõndida mööda vahekäiku

23
00:00:45,300 --> 00:00:48,750
saada brokoli, siis ilmselt peame vaatama kõik muud köögiviljad

24
00:00:48,750 --> 00:00:49,940
enne kui leiad, et brokkoli.

25
00:00:49,940 --> 00:00:54,320
Lineaarne Otsing on näide ühe sellise otsingu meetod - või algoritm.

26
00:00:54,320 --> 00:00:55,550
Nagu nimigi viitab,

27
00:00:55,550 --> 00:00:59,240
Selle meetodi otsima objekti lineaarselt, üksteise järel.

28
00:00:59,240 --> 00:01:02,080
Niisiis, kui te vaatate tulemusi oma lemmik otsingumootor

29
00:01:02,080 --> 00:01:03,850
ja sa loed ette nimekirja tulemusi,

30
00:01:03,850 --> 00:01:05,290
sa kasutad lineaarset otsing.

31
00:01:05,290 --> 00:01:06,830
Okei. Vaatame näiteks.

32
00:01:06,830 --> 00:01:12,600
Ütle meil Arvuloend - 2, 4, 0, 5, 3, 7, 8 ja 1 -

33
00:01:12,600 --> 00:01:15,100
ja me otsime arvu 0.

34
00:01:15,100 --> 00:01:17,290
Ilmselt saate näha, et 0 on kolmandas asendis.

35
00:01:17,290 --> 00:01:19,790
Aga arvutiprogramm ei ole nii õnnelik.

36
00:01:19,790 --> 00:01:22,030
See saab olla ainult "näha" üks number korraga.

37
00:01:22,030 --> 00:01:23,840
Niisiis, alustades alguses nimekirja,

38
00:01:23,840 --> 00:01:25,000
see ainult "näeb" 2.

39
00:01:25,000 --> 00:01:27,860
Programm siis kontrollib - on 2 võrdub 0?

40
00:01:27,860 --> 00:01:30,320
Ilmselt mitte. Nii see läheb edasi järgmise numbri, 4.

41
00:01:30,320 --> 00:01:33,320
Kas 4 võrdset 0? Nope.

42
00:01:33,320 --> 00:01:35,460
Järgmise üks, 0. Ah! Null on võrdne 0-ga.

43
00:01:35,460 --> 00:01:36,920
On meil seda! See on kolmandal kohal.

44
00:01:36,920 --> 00:01:39,660
Okei. Vaatame mõned pseudokoodi.

45
00:01:39,660 --> 00:01:43,320
See on ainult paar rida pikk, kuid vaatame siis üks rida korraga.

46
00:01:43,320 --> 00:01:46,740
Esiteks, ärgem defineerime funktsiooni - ja me nimetame seda lineaarne otsing -

47
00:01:46,740 --> 00:01:49,040
ja see võtab kaks argumenti - võti ja massiivi.

48
00:01:49,040 --> 00:01:50,770
Oluline on, et raha, mida me otsime,

49
00:01:50,770 --> 00:01:53,160
nii eelmises näites, et oli null.

50
00:01:53,160 --> 00:01:55,080
Massiiv on nimekiri numbrid

51
00:01:55,080 --> 00:01:57,180
, mis on kõik väärtused, mida me hakkame otsima.

52
00:01:57,180 --> 00:02:00,010
Niisiis, mida me tahame teha, on me tahame vaadata -

53
00:02:00,010 --> 00:02:02,030
kõik seisukohad, nii algab algusest massiivi

54
00:02:02,030 --> 00:02:05,260
til päris lõpus massiiv - nii pikkus array -

55
00:02:05,260 --> 00:02:07,580
pilk iga positsiooni ja vaadata igaüks.

56
00:02:07,580 --> 00:02:10,000
Nii see on, mida see "eest" loop teeb.

57
00:02:10,000 --> 00:02:11,150
Ja igas asendis, me ei kavatse öelda

58
00:02:11,150 --> 00:02:15,010
"Kas see on väärtus, et praegune olukord võrdne võti, et me otsime?"

59
00:02:15,010 --> 00:02:17,000
Nii et - eelmise näite, võti oli 0 -

60
00:02:17,000 --> 00:02:21,770
nii me ütleme "Kas massiivi positsioonis i võrdne nulliga?"

61
00:02:21,770 --> 00:02:24,640
Kui on, me läheme tagasi "i", sest see on hetkeseis me oleme.

62
00:02:24,640 --> 00:02:25,710
Niisiis, eelmises näites,

63
00:02:25,710 --> 00:02:27,250
see oli kolmandal kohal.

64
00:02:27,250 --> 00:02:29,330
Kui me oleme läbi käinud kogu massiivi

65
00:02:29,330 --> 00:02:30,690
ja me ei leidnud midagi -

66
00:02:30,690 --> 00:02:32,180
nii oletame, et otsisime arv 500

67
00:02:32,180 --> 00:02:33,860
mis selgelt ei olnud, et näiteks -

68
00:02:33,860 --> 00:02:35,860
meil on midagi tagastada,

69
00:02:35,860 --> 00:02:37,140
ja me läheme tagasi -1.

70
00:02:37,140 --> 00:02:39,750
Ja me lihtsalt tagasi -1 sest see positsioon

71
00:02:39,750 --> 00:02:40,990
et ei ole olemas massiiv.

72
00:02:40,990 --> 00:02:43,940
Ja nii see tähendab, et kui sa saad selle tagasi funktsioon

73
00:02:43,940 --> 00:02:46,500
ta ütleb: "Hmm, okei. vist ei leidnud ma midagi.

74
00:02:46,500 --> 00:02:47,930
Nii et 500 kunagi oli seal. "

75
00:02:47,930 --> 00:02:49,700
Tore asi lineaarne otsing on see, et

76
00:02:49,700 --> 00:02:51,060
see saab töötada mis tahes elementide loetelu,

77
00:02:51,060 --> 00:02:52,950
olenemata sellest, kuidas esemed on tellitud.

78
00:02:52,950 --> 00:02:55,540
See ei ole tähtis, kus brokoli on toota vahekäiku.

79
00:02:55,540 --> 00:02:57,070
Niikaua kui te jalutada mööda vahekäiku algusest lõpuni,

80
00:02:57,070 --> 00:02:58,470
sa oled kindlasti leida see,

81
00:02:58,470 --> 00:03:00,800
eeldades poest ei ole otsa brokkoli, muidugi.

82
00:03:00,800 --> 00:03:04,200
Aga see suurimaks tugevuseks on ka see suurim nõrkus.

83
00:03:04,200 --> 00:03:05,340
Oletame, et teil on nimekiri 200 numbrid

84
00:03:05,340 --> 00:03:06,930
et on järjestatud 1-200.

85
00:03:06,930 --> 00:03:09,420
Kui otsite nr 198,

86
00:03:09,420 --> 00:03:11,060
teil on otsida peaaegu kogu nimekiri numbrid

87
00:03:11,060 --> 00:03:12,960
enne leida üks otsite.

88
00:03:12,960 --> 00:03:14,460
Peab olema parem moodus!

89
00:03:14,460 --> 00:03:15,890
Võite kindel olla, et on.

90
00:03:15,890 --> 00:03:17,440
Aga see on teema teise video.

91
00:03:17,440 --> 00:03:19,280
Samuti ärge vihastama!

92
00:03:19,280 --> 00:03:22,650
Lihtsalt, sest lineaarne otsing ei ole parim lahendus igas olukorras,

93
00:03:22,650 --> 00:03:24,190
see ei tähenda, et see ei tule käepärane.

94
00:03:24,190 --> 00:03:27,130
Muidu, kuidas te leiate, et brokkoli on toota vahekäiku?

95
00:03:27,130 --> 00:03:29,910
Minu nimi on Patrick Schmid, ja see on CS50.

96
00:03:29,910 --> 00:03:32,000
[CS50.TV]