1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [Линеарна претрага]

2
00:00:02,430 --> 00:00:04,430
[Патрицк Сцхмид, Универзитет Харвард]

3
00:00:04,430 --> 00:00:07,430
[Тхис Ис ЦС50.] [ЦС50.ТВ]

4
00:00:07,430 --> 00:00:09,440
Претраживање је нешто што вероватно не чешће него што мислите.

5
00:00:09,440 --> 00:00:11,600
Очигледно, сваки пут када отворите веб прегледач

6
00:00:11,600 --> 00:00:12,890
и потрага за веб страници -

7
00:00:12,890 --> 00:00:15,620
или потрага за пријатељима на вашем омиљеном сајту за друштвено умрежавање -

8
00:00:15,620 --> 00:00:16,610
тражите.

9
00:00:16,610 --> 00:00:19,690
Али то је само мали део трагања који радите на дневној бази.

10
00:00:19,690 --> 00:00:21,720
Када желите да пронађете ту једну плаву кошуљу у ормару,

11
00:00:21,720 --> 00:00:23,620
или да савршено црвене блузе за ту прилику,

12
00:00:23,620 --> 00:00:24,730
ви тражите.

13
00:00:24,730 --> 00:00:26,640
Када одете у продавницу да никада нисам била од пре,

14
00:00:26,640 --> 00:00:28,590
и ви сте у потрази за броколи на пијаци пролаз

15
00:00:28,590 --> 00:00:29,650
ви тражите.

16
00:00:29,650 --> 00:00:31,050
Оно што можда почели да примећују

17
00:00:31,050 --> 00:00:32,820
је да, у зависности од тога шта сте тражили

18
00:00:32,820 --> 00:00:35,340
или како се ствари су организовани када сте у потрази за њих

19
00:00:35,340 --> 00:00:37,670
она има утицај на то како тражите.

20
00:00:37,670 --> 00:00:40,990
На пример, ако ваше кошуље су виси у ормару,

21
00:00:40,990 --> 00:00:42,840
вероватно да га само покупити без много тражи.

22
00:00:42,840 --> 00:00:45,300
Ако сте под претпоставком да морају да пешаче до олтара

23
00:00:45,300 --> 00:00:48,750
добити броколи, вероватно имате да погледате на свим другим поврћем

24
00:00:48,750 --> 00:00:49,940
пре него што вам је тај броколи.

25
00:00:49,940 --> 00:00:54,320
Линеарна претрага је пример једне такве методе у потрази - или алгоритму.

26
00:00:54,320 --> 00:00:55,550
Као што назив имплицира,

27
00:00:55,550 --> 00:00:59,240
овај метод трага за ставке у линеарном моду, једна иза друге.

28
00:00:59,240 --> 00:01:02,080
Дакле, када гледамо резултате из вашег омиљеног претраживача

29
00:01:02,080 --> 00:01:03,850
и ви прочитате доле листу резултата,

30
00:01:03,850 --> 00:01:05,290
користите линеарну претрагу.

31
00:01:05,290 --> 00:01:06,830
Ок. Погледајмо један пример.

32
00:01:06,830 --> 00:01:12,600
Рецимо имамо списак бројева - 2, 4, 0, 5, 3, 7, 8, и 1 -

33
00:01:12,600 --> 00:01:15,100
а ми тражимо број 0.

34
00:01:15,100 --> 00:01:17,290
Очигледно, само се види да је 0 у трећем положају.

35
00:01:17,290 --> 00:01:19,790
Али, компјутерски програм није толико среће.

36
00:01:19,790 --> 00:01:22,030
То само може да "види" један број у једном тренутку.

37
00:01:22,030 --> 00:01:23,840
Дакле, са почетком у почетку листе,

38
00:01:23,840 --> 00:01:25,000
она само "види" 2.

39
00:01:25,000 --> 00:01:27,860
Програм затим проверава - је 2 једнако 0?

40
00:01:27,860 --> 00:01:30,320
Очигледно није. Тако то иде на следећи број, 4.

41
00:01:30,320 --> 00:01:33,320
Да ли 4 једнаке 0? Јок.

42
00:01:33,320 --> 00:01:35,460
Следећи један, 0. Ах! Нула је једнак 0.

43
00:01:35,460 --> 00:01:36,920
Ту га имамо! То је у трећем месту.

44
00:01:36,920 --> 00:01:39,660
Ок. Хајде да погледамо неке Псеудокод.

45
00:01:39,660 --> 00:01:43,320
То је само пар линија дугих, али хајде да погледамо на то једну линију у исто време.

46
00:01:43,320 --> 00:01:46,740
Прво, хајде да дефинишемо функцију - и ми ћемо га зову линеарна претрага -

47
00:01:46,740 --> 00:01:49,040
и то траје два аргумента - тастер и низа.

48
00:01:49,040 --> 00:01:50,770
Кључ је да вредност која тражимо,

49
00:01:50,770 --> 00:01:53,160
тако да је у претходном примеру, то је био нула.

50
00:01:53,160 --> 00:01:55,080
Низ је листа бројева

51
00:01:55,080 --> 00:01:57,180
које има све вредности које смо ишли да претражите.

52
00:01:57,180 --> 00:02:00,010
Дакле, оно што ми желимо да урадимо јесте желимо да погледамо -

53
00:02:00,010 --> 00:02:02,030
из свих позиција, па почетком у самом почетку низа

54
00:02:02,030 --> 00:02:05,260
тил самом крају низа - тако дужине низа -

55
00:02:05,260 --> 00:02:07,580
погледати сваког положаја и проверите сваки од њих.

56
00:02:07,580 --> 00:02:10,000
Дакле, то је оно што је "за" петља се ради.

57
00:02:10,000 --> 00:02:11,150
И на свакој позицији, ми ћемо рећи

58
00:02:11,150 --> 00:02:15,010
"Да ли је та вредност у тој тренутној позицији једнак тастеру да тражимо?"

59
00:02:15,010 --> 00:02:17,000
Дакле - у претходном примеру, кључ је 0 -

60
00:02:17,000 --> 00:02:21,770
тако да смо се говорећи: "Да ли је низ на позицији сам једнак нули?"

61
00:02:21,770 --> 00:02:24,640
Ако јесте, ми ћемо вратити 'ја', јер је то тренутна позиција смо.

62
00:02:24,640 --> 00:02:25,710
Дакле, у претходном примеру,

63
00:02:25,710 --> 00:02:27,250
то је био трећи положај.

64
00:02:27,250 --> 00:02:29,330
Ако смо прошли кроз цео низ

65
00:02:29,330 --> 00:02:30,690
и нисмо нашли ништа -

66
00:02:30,690 --> 00:02:32,180
па рецимо да смо у потрази за број 500

67
00:02:32,180 --> 00:02:33,860
што јасно није био у том примеру -

68
00:02:33,860 --> 00:02:35,860
морамо се вратити нешто,

69
00:02:35,860 --> 00:02:37,140
и ми ћемо вратити -1.

70
00:02:37,140 --> 00:02:39,750
А ми се враћамо -1 јер је то став

71
00:02:39,750 --> 00:02:40,990
који не постоји у низу.

72
00:02:40,990 --> 00:02:43,940
И то значи да када га добијете назад од функције

73
00:02:43,940 --> 00:02:46,500
пише "Хм, ок. ваљда нисам нашао ништа.

74
00:02:46,500 --> 00:02:47,930
Тако да 500 никада није био тамо. "

75
00:02:47,930 --> 00:02:49,700
Лепа ствар у вези са линеарном претрази је да

76
00:02:49,700 --> 00:02:51,060
да ће радити на било којој листи ставки,

77
00:02:51,060 --> 00:02:52,950
без обзира како су ствари распоређене.

78
00:02:52,950 --> 00:02:55,540
Није битно где се броколи је на пијаци пролазу.

79
00:02:55,540 --> 00:02:57,070
Докле год хода низ пролаз од почетка до краја,

80
00:02:57,070 --> 00:02:58,470
сте обавезни да га пронађе,

81
00:02:58,470 --> 00:03:00,800
претпостављајући продавницу није понестало броколија, наравно.

82
00:03:00,800 --> 00:03:04,200
Али то је највећа снага је такође то је највећа слабост.

83
00:03:04,200 --> 00:03:05,340
Рецимо да имате листу двеста бројева

84
00:03:05,340 --> 00:03:06,930
које су сортиране од 1 до 200.

85
00:03:06,930 --> 00:03:09,420
Ако сте у потрази за број 198,

86
00:03:09,420 --> 00:03:11,060
морате да претражите готово читаву листу бројева

87
00:03:11,060 --> 00:03:12,960
пре него што пронађете ону коју тражите.

88
00:03:12,960 --> 00:03:14,460
Мора постојати бољи начин!

89
00:03:14,460 --> 00:03:15,890
Будите сигурни да има.

90
00:03:15,890 --> 00:03:17,440
Али, то је тема за неки други видео.

91
00:03:17,440 --> 00:03:19,280
Такође, не узрујавати!

92
00:03:19,280 --> 00:03:22,650
Само зато што линеарно претраживање није најбоље решење у свим ситуацијама,

93
00:03:22,650 --> 00:03:24,190
то не значи да то не долази у руци.

94
00:03:24,190 --> 00:03:27,130
Иначе, како би вам тај броколи на пијаци пролаз?

95
00:03:27,130 --> 00:03:29,910
Моје име је Патрик Шмит, а то је ЦС50.

96
00:03:29,910 --> 00:03:32,000
[ЦС50.ТВ]