1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [Linearni Traži]

2
00:00:02,430 --> 00:00:04,430
[Patrick Schmid, Sveučilište Harvard]

3
00:00:04,430 --> 00:00:07,430
[This Is CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
Tražim je nešto što vjerojatno ne češće nego što mislite.

5
00:00:09,440 --> 00:00:11,600
Očito, svaki put kada otvorite web preglednik

6
00:00:11,600 --> 00:00:12,890
i potraga za web stranice -

7
00:00:12,890 --> 00:00:15,620
ili traži za svoje prijatelje na svoj omiljeni socijalna mreža položaj -

8
00:00:15,620 --> 00:00:16,610
vi ste u potrazi.

9
00:00:16,610 --> 00:00:19,690
No, to je samo mali dio od traženja da se bavite na dnevnoj bazi.

10
00:00:19,690 --> 00:00:21,720
Kada želite da otkrijete da jedan plavu košulju u ormaru,

11
00:00:21,720 --> 00:00:23,620
ili da savršena crvena bluza za tu prigodu,

12
00:00:23,620 --> 00:00:24,730
ste u potrazi.

13
00:00:24,730 --> 00:00:26,640
Kad idete u dućan da ste nikada nije bio na prije,

14
00:00:26,640 --> 00:00:28,590
a vi ste u potrazi za brokule u proizvode prolaz

15
00:00:28,590 --> 00:00:29,650
ste u potrazi.

16
00:00:29,650 --> 00:00:31,050
Ono što svibanj su počeli da se primjetiti

17
00:00:31,050 --> 00:00:32,820
je da, ovisno o tome što ste u potrazi za

18
00:00:32,820 --> 00:00:35,340
ili kako predmeti su organizirani kada ste u potrazi za njima

19
00:00:35,340 --> 00:00:37,670
ima utjecaj na to kako se traži.

20
00:00:37,670 --> 00:00:40,990
Na primjer, ako su vaše košulje visi u ormaru,

21
00:00:40,990 --> 00:00:42,840
vjerojatno možete samo to podići bez puno traži.

22
00:00:42,840 --> 00:00:45,300
Ako ste pod pretpostavkom da morate hodati niz prolaz

23
00:00:45,300 --> 00:00:48,750
dobiti brokulu, vjerojatno morati gledati na svim drugim povrćem

24
00:00:48,750 --> 00:00:49,940
prije vam da brokulu.

25
00:00:49,940 --> 00:00:54,320
Linearni Pretraživanje je primjer jednog takvog potrazi metodom - ili algoritam.

26
00:00:54,320 --> 00:00:55,550
Kao što naziv implicira,

27
00:00:55,550 --> 00:00:59,240
ova metoda traži za stavku u linearno, jedan iza drugoga.

28
00:00:59,240 --> 00:01:02,080
Dakle, kada ste u potrazi na rezultate iz svoje omiljene tražilice

29
00:01:02,080 --> 00:01:03,850
a vi pročitajte dolje na popisu rezultata,

30
00:01:03,850 --> 00:01:05,290
koristite linearni pretraživanje.

31
00:01:05,290 --> 00:01:06,830
Ok. Pogledajmo primjer.

32
00:01:06,830 --> 00:01:12,600
Recimo da imamo popis brojeva - 2, 4, 0, 5, 3, 7, 8 i 1 -

33
00:01:12,600 --> 00:01:15,100
i mi smo u potrazi za broj 0.

34
00:01:15,100 --> 00:01:17,290
Očito, možete samo vidjeti da je 0 u trećoj poziciji.

35
00:01:17,290 --> 00:01:19,790
No, računalni program nije da je sretan.

36
00:01:19,790 --> 00:01:22,030
To samo može "vidjeti" jedan broj u isto vrijeme.

37
00:01:22,030 --> 00:01:23,840
Dakle, s početkom u početku popisa,

38
00:01:23,840 --> 00:01:25,000
to je samo "vidi" je 2.

39
00:01:25,000 --> 00:01:27,860
Program zatim provjerava - je dva jednaka 0?

40
00:01:27,860 --> 00:01:30,320
Očito ne. Tako to ide na sljedeći broj, četiri.

41
00:01:30,320 --> 00:01:33,320
Da li četiri jednaka 0? Nope.

42
00:01:33,320 --> 00:01:35,460
Sljedeći, 0. Ah! Zero je jednaka 0.

43
00:01:35,460 --> 00:01:36,920
Tu smo ga! To je u trećem položaju.

44
00:01:36,920 --> 00:01:39,660
Ok. Pogledajmo neke pseudocode.

45
00:01:39,660 --> 00:01:43,320
To je samo par redaka dugo, ali pogledajmo to jedna linija na vrijeme.

46
00:01:43,320 --> 00:01:46,740
Prvo, neka je definirati funkciju - i mi ćemo ga zovu linearni pretraga -

47
00:01:46,740 --> 00:01:49,040
i to traje dva argumenta - ključ i lepezu.

48
00:01:49,040 --> 00:01:50,770
Ključno je da se vrijednost da smo u potrazi za,

49
00:01:50,770 --> 00:01:53,160
tako da u prethodnom primjeru, koji je bio nula.

50
00:01:53,160 --> 00:01:55,080
Niz je popis brojeva

51
00:01:55,080 --> 00:01:57,180
da ima sve vrijednosti koje ćemo tražiti.

52
00:01:57,180 --> 00:02:00,010
Dakle, ono što želim učiniti je da želimo pogledati -

53
00:02:00,010 --> 00:02:02,030
iz svih položaja, tako da počinje na samom početku niza

54
00:02:02,030 --> 00:02:05,260
til samom kraju niza - tako duljini polja -

55
00:02:05,260 --> 00:02:07,580
pogledati svaki položaj i provjerite svaki.

56
00:02:07,580 --> 00:02:10,000
Dakle, to je ono što je "za" petlja se radi.

57
00:02:10,000 --> 00:02:11,150
I na svakoj poziciji, idemo reći

58
00:02:11,150 --> 00:02:15,010
"Je li to vrijednost u tom trenutnu poziciju jednakom ključu da smo u potrazi za?"

59
00:02:15,010 --> 00:02:17,000
Dakle - u prethodnom primjeru opet, ključ je 0 -

60
00:02:17,000 --> 00:02:21,770
tako da smo se govoreći: "Je li polje na poziciji ja jednaka nuli?"

61
00:02:21,770 --> 00:02:24,640
Ako je, idemo se vratiti 'ja', jer to je trenutna pozicija smo na.

62
00:02:24,640 --> 00:02:25,710
Dakle, u prethodnom primjeru,

63
00:02:25,710 --> 00:02:27,250
da je treće mjesto.

64
00:02:27,250 --> 00:02:29,330
Ako smo prošli kroz cijeli niz

65
00:02:29,330 --> 00:02:30,690
i nismo našli ništa -

66
00:02:30,690 --> 00:02:32,180
pa ajmo reći da smo bili u potrazi za brojem 500

67
00:02:32,180 --> 00:02:33,860
koji jasno nije bio u tom primjeru -

68
00:02:33,860 --> 00:02:35,860
moramo se vratiti nešto,

69
00:02:35,860 --> 00:02:37,140
i da ćemo se vratiti -1.

70
00:02:37,140 --> 00:02:39,750
I mi smo samo vraća -1, jer to je položaj

71
00:02:39,750 --> 00:02:40,990
da ne postoji u polju.

72
00:02:40,990 --> 00:02:43,940
I tako to znači kada vam ga vratiti iz funkcije

73
00:02:43,940 --> 00:02:46,500
ona kaže: "Hm, ok. mislim da nisu pronašli ništa.

74
00:02:46,500 --> 00:02:47,930
Tako da 500 nikada nije bio tamo. "

75
00:02:47,930 --> 00:02:49,700
Lijepo je stvar o linearnom potrazi je da

76
00:02:49,700 --> 00:02:51,060
to će raditi na bilo kojem popisu stavki,

77
00:02:51,060 --> 00:02:52,950
bez obzira na to kako se stavke naredio.

78
00:02:52,950 --> 00:02:55,540
Nije bitno gdje je brokula u proizvode prolaz.

79
00:02:55,540 --> 00:02:57,070
Dokle god hoda niz prolaz od početka do kraja,

80
00:02:57,070 --> 00:02:58,470
vi ste dužni da ga pronaći,

81
00:02:58,470 --> 00:03:00,800
pretpostavljajući dućan nije ponestalo brokule, naravno.

82
00:03:00,800 --> 00:03:04,200
No, to je najveća snaga je također da je najveća slabost.

83
00:03:04,200 --> 00:03:05,340
Recimo da imate popis dvjesto brojeva

84
00:03:05,340 --> 00:03:06,930
koji su razvrstani 1-200.

85
00:03:06,930 --> 00:03:09,420
Ako ste u potrazi za brojem 198,

86
00:03:09,420 --> 00:03:11,060
morate tražiti gotovo cijeli popis brojeva

87
00:03:11,060 --> 00:03:12,960
prije nego što pronađete onu koju tražite.

88
00:03:12,960 --> 00:03:14,460
Mora postojati bolji način!

89
00:03:14,460 --> 00:03:15,890
Budite uvjereni da postoji.

90
00:03:15,890 --> 00:03:17,440
Ali, to je tema za drugi video.

91
00:03:17,440 --> 00:03:19,280
Također, ne uzrujavati!

92
00:03:19,280 --> 00:03:22,650
Samo zato linearno pretraživanje nije najbolje rješenje u svim situacijama,

93
00:03:22,650 --> 00:03:24,190
to ne znači da to ne dolazi u ruci.

94
00:03:24,190 --> 00:03:27,130
Inače, kako bi vam tu brokulu u proizvoditi prolaz?

95
00:03:27,130 --> 00:03:29,910
Moje ime je Patrick Schmid, a ovo je CS50.

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