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

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

3
00:00:04,430 --> 00:00:07,430
[To je CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
Iskanje je nekaj, kar ste verjetno bolj pogosto, kot si mislite.

5
00:00:09,440 --> 00:00:11,600
Očitno je, da vsakič, ko odpre spletni brskalnik

6
00:00:11,600 --> 00:00:12,890
in iskanje spletne strani -

7
00:00:12,890 --> 00:00:15,620
ali iskanje za svoje prijatelje na vaš najljubši socialne mreže na mestu -

8
00:00:15,620 --> 00:00:16,610
iščete.

9
00:00:16,610 --> 00:00:19,690
Ampak to je samo majhen del iskanja, ki vam na dnevni osnovi.

10
00:00:19,690 --> 00:00:21,720
Če želite, da bi našli, da je ena modro srajco v omari,

11
00:00:21,720 --> 00:00:23,620
ali da je popolna rdeča bluza za to priložnost,

12
00:00:23,620 --> 00:00:24,730
iščete.

13
00:00:24,730 --> 00:00:26,640
Ko greste v trgovino, da še nikoli niste bili na prej,

14
00:00:26,640 --> 00:00:28,590
in iščete brokoli proizvajajo v hodniku

15
00:00:28,590 --> 00:00:29,650
iščete.

16
00:00:29,650 --> 00:00:31,050
Kaj ste morda začeli opažati

17
00:00:31,050 --> 00:00:32,820
je to odvisno od tega, kaj iščete

18
00:00:32,820 --> 00:00:35,340
ali kako predmeti so organizirani, ko ste iskali za njih

19
00:00:35,340 --> 00:00:37,670
učinkujejo na način, kako iskati.

20
00:00:37,670 --> 00:00:40,990
Na primer, če vaše srajce visijo v omari,

21
00:00:40,990 --> 00:00:42,840
lahko verjetno samo izločiti, ne da bi veliko iskanja.

22
00:00:42,840 --> 00:00:45,300
Če ste ob predpostavki, da imate na sprehod do oltarja

23
00:00:45,300 --> 00:00:48,750
da bi dobili brokoli, boste verjetno morali pogledati vse druge zelenjave

24
00:00:48,750 --> 00:00:49,940
preden boste ugotovili, da brokoli.

25
00:00:49,940 --> 00:00:54,320
Linearni Iskanje je primer take metode Iskanje - ali algoritem.

26
00:00:54,320 --> 00:00:55,550
Kot pove že ime,

27
00:00:55,550 --> 00:00:59,240
Ta metoda poišče element v linearno, eden za drugim.

28
00:00:59,240 --> 00:01:02,080
Torej, če ste iskali na rezultate iz vašega priljubljenega iskalnika

29
00:01:02,080 --> 00:01:03,850
in ste prebrali določitvi seznama rezultatov,

30
00:01:03,850 --> 00:01:05,290
uporabljate linearno iskanje.

31
00:01:05,290 --> 00:01:06,830
Ok. Oglejmo si primer.

32
00:01:06,830 --> 00:01:12,600
Pravijo, da imamo seznam številk - 2, 4, 0, 5, 3, 7, 8 in 1 -

33
00:01:12,600 --> 00:01:15,100
in iščemo za številko 0.

34
00:01:15,100 --> 00:01:17,290
Očitno je, da lahko samo videli, da je 0 na tretjem mestu.

35
00:01:17,290 --> 00:01:19,790
Ampak, računalniški program, ki ni srečen.

36
00:01:19,790 --> 00:01:22,030
To je lahko samo "videti" eno številko naenkrat.

37
00:01:22,030 --> 00:01:23,840
Torej, z začetkom na začetku seznama,

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

39
00:01:25,000 --> 00:01:27,860
Program nato preveri - je 2 enak 0?

40
00:01:27,860 --> 00:01:30,320
Očitno ne. Torej, gre na naslednjo številko, 4.

41
00:01:30,320 --> 00:01:33,320
Ali 4 enake 0? Ne.

42
00:01:33,320 --> 00:01:35,460
Naslednji 1, 0. Ah! Zero je enak 0.

43
00:01:35,460 --> 00:01:36,920
Tam smo ga imeli! To je v tretjem mestu.

44
00:01:36,920 --> 00:01:39,660
Ok. Oglejmo si nekaj psevdokod.

45
00:01:39,660 --> 00:01:43,320
To je samo nekaj vrstic, vendar pa si poglejmo na to eno vrstico naenkrat.

46
00:01:43,320 --> 00:01:46,740
Prvič, kaj je opredeliti vlogo - in bomo rekli linearno iskanje -

47
00:01:46,740 --> 00:01:49,040
in to traja dva argumenta - ključ in paleto.

48
00:01:49,040 --> 00:01:50,770
Ključno je, da se vrednost, ki jo iščemo,

49
00:01:50,770 --> 00:01:53,160
Tako v prejšnjem primeru, da je bila enaka nič.

50
00:01:53,160 --> 00:01:55,080
Matrika je seznam številk

51
00:01:55,080 --> 00:01:57,180
ki ima vse vrednosti, ki jih bomo iskali.

52
00:01:57,180 --> 00:02:00,010
Torej, kaj želimo storiti, je, da smo želeli videti na -

53
00:02:00,010 --> 00:02:02,030
iz vseh položajev, tako da se začne na samem začetku niza

54
00:02:02,030 --> 00:02:05,260
til samega konca niza - tako na dolžino niza -

55
00:02:05,260 --> 00:02:07,580
pogled na vsako mesto in preverite vsako posebej.

56
00:02:07,580 --> 00:02:10,000
Torej, to je tisto, da je "za" zanka počne.

57
00:02:10,000 --> 00:02:11,150
In v vsakem položaju, bomo rekli

58
00:02:11,150 --> 00:02:15,010
"Ali je ta vrednost v tej trenutni položaj, ki je enak ključu, ki ga iščete?"

59
00:02:15,010 --> 00:02:17,000
Torej - v prejšnjem primeru še enkrat, ključ je bil 0 -

60
00:02:17,000 --> 00:02:21,770
zato smo rekli: "Je matrika na položaju i enaka nič?"

61
00:02:21,770 --> 00:02:24,640
Če je tako, bomo vrnili "i", ker to je trenutni položaj smo na.

62
00:02:24,640 --> 00:02:25,710
Torej, v prejšnjem primeru,

63
00:02:25,710 --> 00:02:27,250
da je tretje mesto.

64
00:02:27,250 --> 00:02:29,330
Če smo šli skozi celoten niz

65
00:02:29,330 --> 00:02:30,690
in nismo našli ničesar -

66
00:02:30,690 --> 00:02:32,180
Tako recimo smo iskali številko 500

67
00:02:32,180 --> 00:02:33,860
ki očitno ni bil v tem primeru -

68
00:02:33,860 --> 00:02:35,860
bomo morali vrniti nekaj,

69
00:02:35,860 --> 00:02:37,140
in bomo -1 vrniti.

70
00:02:37,140 --> 00:02:39,750
In mi smo pravkar vrnil -1, ker je to stališče

71
00:02:39,750 --> 00:02:40,990
ki ne obstaja v polje.

72
00:02:40,990 --> 00:02:43,940
In tako to pomeni, da ko si jo dobil nazaj od funkcije

73
00:02:43,940 --> 00:02:46,500
pravi: "Hm, okej. Mislim, da niso našli ničesar.

74
00:02:46,500 --> 00:02:47,930
Tako, da 500 ni bilo nikoli tam. "

75
00:02:47,930 --> 00:02:49,700
Za lepo stvar je, da se linearno iskanje

76
00:02:49,700 --> 00:02:51,060
da bo delovalo na nobenem seznamu predmetov,

77
00:02:51,060 --> 00:02:52,950
ne glede na to, kako se naročiti postavke.

78
00:02:52,950 --> 00:02:55,540
Ni važno, če je brokoli je v proizvajajo oltarja.

79
00:02:55,540 --> 00:02:57,070
Dokler boste sprehod do oltarja od začetka do konca,

80
00:02:57,070 --> 00:02:58,470
ste dolžni najti,

81
00:02:58,470 --> 00:03:00,800
ob predpostavki, da trgovina ni zmanjkalo brokoli, seveda.

82
00:03:00,800 --> 00:03:04,200
Ampak to je največja moč je tudi, da je največja slabost.

83
00:03:04,200 --> 00:03:05,340
Recimo, da imate seznam 200 številk

84
00:03:05,340 --> 00:03:06,930
, ki so razporejene 1-200.

85
00:03:06,930 --> 00:03:09,420
Če iščete za številko 198,

86
00:03:09,420 --> 00:03:11,060
boste morali iskati skoraj celoten seznam številk

87
00:03:11,060 --> 00:03:12,960
preden boste našli enega, ki ga iščete.

88
00:03:12,960 --> 00:03:14,460
Mora biti boljši način!

89
00:03:14,460 --> 00:03:15,890
Bodite prepričani, da je.

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

91
00:03:17,440 --> 00:03:19,280
Prav, ne skrbi!

92
00:03:19,280 --> 00:03:22,650
Samo zato, ker linearni iskanje ni najboljša rešitev v vseh situacijah,

93
00:03:22,650 --> 00:03:24,190
to ne pomeni, da ne pride v poštev.

94
00:03:24,190 --> 00:03:27,130
V nasprotnem primeru, kako bi našli, da je brokoli v hodniku proizvajajo?

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

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