1
00:00:00,000 --> 00:00:03,346
>> [Мусиц плаиинг]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> Даг Ллоид: У реду.

4
00:00:06,220 --> 00:00:08,140
Дакле, бинарна претрага је
алгоритам можемо користити

5
00:00:08,140 --> 00:00:10,530
да пронађе елемент унутар низа.

6
00:00:10,530 --> 00:00:14,710
За разлику од линеарне претраге, захтијева
посебан услов да се претходно састали,

7
00:00:14,710 --> 00:00:19,020
али тако је много ефикасније да
тај услов је, у ствари, срео.

8
00:00:19,020 --> 00:00:20,470
>> Дакле, шта је ту је идеја?

9
00:00:20,470 --> 00:00:21,780
то је завади па владај.

10
00:00:21,780 --> 00:00:25,100
Желимо да се смањи величину
потрага простор за пола сваки пут

11
00:00:25,100 --> 00:00:27,240
како би се пронашли број одредишта.

12
00:00:27,240 --> 00:00:29,520
Ово је где је то услов
долази до изражаја, ипак.

13
00:00:29,520 --> 00:00:32,740
Можемо само да искористе моћ
елиминисања половина елемената

14
00:00:32,740 --> 00:00:36,070
без да гледа
их ако је низ сортира.

15
00:00:36,070 --> 00:00:39,200
>> Ако је то потпуна забуна,
не можемо само из руке

16
00:00:39,200 --> 00:00:42,870
одбацити половина елемената, јер је
ми не знамо шта ћемо одбацивање.

17
00:00:42,870 --> 00:00:45,624
Али, ако је низ сортира,
можемо то да урадимо, јер смо ми

18
00:00:45,624 --> 00:00:48,040
знам да је све до
лево где тренутно смо

19
00:00:48,040 --> 00:00:50,500
мора бити нижа од
вредност тренутно у смо.

20
00:00:50,500 --> 00:00:52,300
И све до
Право где смо

21
00:00:52,300 --> 00:00:55,040
мора бити већи од вредности
тренутно гледамо.

22
00:00:55,040 --> 00:00:58,710
>> Дакле, шта је Псеудокод
кораци за бинарни потрази?

23
00:00:58,710 --> 00:01:02,310
Понављамо овај процес док се
низ или како да наставимо путем,

24
00:01:02,310 --> 00:01:07,740
суб низови, мањи комади
оригинални низ, је величине 0.

25
00:01:07,740 --> 00:01:10,960
Израчунајте средиште
тренутне под низа.

26
00:01:10,960 --> 00:01:14,460
>> Ако је вредност тражиш је
у том елементу низа, стоп.

27
00:01:14,460 --> 00:01:15,030
Нашао си га.

28
00:01:15,030 --> 00:01:16,550
Одлично.

29
00:01:16,550 --> 00:01:19,610
У супротном, ако је мета
мање него што је на средини,

30
00:01:19,610 --> 00:01:23,430
па ако вредности гледамо
за мањи од оног што видимо,

31
00:01:23,430 --> 00:01:26,780
понављам овај процес, али
промените крајњу тачку, уместо

32
00:01:26,780 --> 00:01:29,300
да буде оригинална
завршити читав низ,

33
00:01:29,300 --> 00:01:34,110
да буде само на лево
где смо само гледали.

34
00:01:34,110 --> 00:01:38,940
>> Знали смо да је средњи био превисок,
или мета била мања од средини,

35
00:01:38,940 --> 00:01:42,210
а тако мора постојати, иф ит
уопште постоји у низу,

36
00:01:42,210 --> 00:01:44,660
негде лево од средње вредности.

37
00:01:44,660 --> 00:01:48,120
И тако ћемо поставити низ
локација само са леве стране

38
00:01:48,120 --> 00:01:51,145
на средњој тачки као нови крајњу тачку.

39
00:01:51,145 --> 00:01:53,770
Насупрот томе, ако је мета
већи него што је на средини,

40
00:01:53,770 --> 00:01:55,750
радимо потпуно исти
процес, већ смо

41
00:01:55,750 --> 00:01:59,520
промените почетну тачку да буде
само десно од средње вредности

42
00:01:59,520 --> 00:02:00,680
ми само израчунати.

43
00:02:00,680 --> 00:02:03,220
А онда, почињемо поново процес.

44
00:02:03,220 --> 00:02:05,220
>> Хајде да визуализују, ОК?

45
00:02:05,220 --> 00:02:08,620
Дакле, постоји много дешава и овде,
али овде је низ од 15 елемената.

46
00:02:08,620 --> 00:02:11,400
И ми ћемо бити праћење
а много више ствари овај пут.

47
00:02:11,400 --> 00:02:13,870
Дакле, у линеарном потрази смо били
само брину о мету.

48
00:02:13,870 --> 00:02:15,869
Али овај пут желимо да
брига где смо ми

49
00:02:15,869 --> 00:02:18,480
почиње да види гдје,
стајемо у потрази,

50
00:02:18,480 --> 00:02:21,876
и шта је средиште
тренутне низа.

51
00:02:21,876 --> 00:02:23,250
Дакле, идемо са бинарном претрагу.

52
00:02:23,250 --> 00:02:25,290
Ми смо прилично добро да иде, зар не?

53
00:02:25,290 --> 00:02:28,650
Само ћу да спустим
испод овде скуп индекса.

54
00:02:28,650 --> 00:02:32,430
Ово је у суштини само оно што елемената
од низа говоримо о.

55
00:02:32,430 --> 00:02:34,500
Са линеарном потрази смо
брига, пошто смо ми

56
00:02:34,500 --> 00:02:36,800
Морам да знам колико
Елементи смо итератинг преко,

57
00:02:36,800 --> 00:02:40,010
али не заправо брига шта
елеменат тренутно гледамо.

58
00:02:40,010 --> 00:02:41,014
У бинарном претрагом, знамо.

59
00:02:41,014 --> 00:02:42,930
И тако они су само
тамо као мали водич.

60
00:02:42,930 --> 00:02:44,910
>> Дакле, можемо да почнемо, зар не?

61
00:02:44,910 --> 00:02:46,240
Па, не баш.

62
00:02:46,240 --> 00:02:48,160
Запамтите шта сам рекао
о бинарном сеарцх?

63
00:02:48,160 --> 00:02:50,955
Не можемо то урадити по принципу
мусиц низ иначе,

64
00:02:50,955 --> 00:02:55,820
ми не гарантује да је
извесни елементи или вредности нису

65
00:02:55,820 --> 00:02:57,650
као случајно
одбачена када смо

66
00:02:57,650 --> 00:02:59,920
одлучи да игнорише половини низа.

67
00:02:59,920 --> 00:03:02,574
>> Дакле, први корак са бинарном потрази
је морате имати сортиране низ.

68
00:03:02,574 --> 00:03:05,240
И можете користити било који сортирање
алгоритми смо говорили

69
00:03:05,240 --> 00:03:06,700
да те на тај положај.

70
00:03:06,700 --> 00:03:10,370
Дакле, сада смо у позицији где
можемо обављати бинарни претрагу.

71
00:03:10,370 --> 00:03:12,560
>> Дакле, хајде да поновите поступак
корак по корак и задржати

72
00:03:12,560 --> 00:03:14,830
траг шта се дешава како идемо.

73
00:03:14,830 --> 00:03:17,980
Дакле, прво морамо да урадимо је да израчуна
средиште тренутне низа.

74
00:03:17,980 --> 00:03:20,620
Па, ми ћемо рећи да смо прво
све, у потрази за вредност 19.

75
00:03:20,620 --> 00:03:22,290
Покушавамо да нађемо број 19.

76
00:03:22,290 --> 00:03:25,380
Први елемент овога
низ се налази на индексу нула,

77
00:03:25,380 --> 00:03:28,880
а последњи елемент овога
низ се налази на индекс 14.

78
00:03:28,880 --> 00:03:31,430
И тако ћемо назвати оне почетак и крај.

79
00:03:31,430 --> 00:03:35,387
>> Тако смо укупну средиште по
додајући 0 плус 14 подељено са 2;

80
00:03:35,387 --> 00:03:36,720
прилично јасно средину.

81
00:03:36,720 --> 00:03:40,190
И можемо рећи да
средину је сада 7.

82
00:03:40,190 --> 00:03:43,370
Тако је 15 оно што тражите?

83
00:03:43,370 --> 00:03:43,940
Не то није.

84
00:03:43,940 --> 00:03:45,270
Тражимо 19.

85
00:03:45,270 --> 00:03:49,400
Али ми знамо да 19 је већа
него што смо нашли на средини.

86
00:03:49,400 --> 00:03:52,470
>> Дакле, шта можемо да урадимо је
промените почетну тачку

87
00:03:52,470 --> 00:03:57,280
да буде само на десно од
средину, и поновите поступак поново.

88
00:03:57,280 --> 00:04:01,690
И када то урадимо, ми сада рећи
Нови почетак Поента је низ локација 8.

89
00:04:01,690 --> 00:04:07,220
Оно што смо урадили је ефикасно
игнорисао све са леве стране 15.

90
00:04:07,220 --> 00:04:09,570
Уклонили смо пола
проблема, а сада,

91
00:04:09,570 --> 00:04:13,510
уместо да претражујете
преко 15 елемената у нашем низу,

92
00:04:13,510 --> 00:04:15,610
имамо само да потражите преко 7.

93
00:04:15,610 --> 00:04:17,706
Тако 8 је нова почетна тачка.

94
00:04:17,706 --> 00:04:19,600
14 је и даље крајња тачка.

95
00:04:19,600 --> 00:04:21,430
>> А сада, идемо кроз ово поново.

96
00:04:21,430 --> 00:04:22,810
Рачунамо нови средиште.

97
00:04:22,810 --> 00:04:27,130
8, плус 14 је 22, подељено са 2 је 11.

98
00:04:27,130 --> 00:04:28,660
Да ли је то оно што тражите?

99
00:04:28,660 --> 00:04:30,110
Не то није.

100
00:04:30,110 --> 00:04:32,930
Тражимо вредности који је
мање него што смо управо пронашли.

101
00:04:32,930 --> 00:04:34,721
Тако ћемо поновити
Опет тај процес.

102
00:04:34,721 --> 00:04:38,280
Идемо да промените крајњу тачку на
бити само са леве стране средње вредности.

103
00:04:38,280 --> 00:04:41,800
Дакле, нова крајња тачка постаје 10.

104
00:04:41,800 --> 00:04:44,780
И сада, то је само део
Низ морамо да тражимо.

105
00:04:44,780 --> 00:04:48,460
Дакле, сада смо елиминисани
12 од 15 елемената.

106
00:04:48,460 --> 00:04:51,550
Знамо да ако 19
постоји у низу, да

107
00:04:51,550 --> 00:04:57,210
мора да постоји негде између елемента
број 8 и елемент број 10.

108
00:04:57,210 --> 00:04:59,400
>> Тако да смо израчунали нове средиште поново.

109
00:04:59,400 --> 00:05:02,900
8, плус 10 је 18, подељено са 2 је 9.

110
00:05:02,900 --> 00:05:05,074
И у овом случају, види,
мета је на средини.

111
00:05:05,074 --> 00:05:06,740
Нашли смо управо оно што ми тражимо.

112
00:05:06,740 --> 00:05:07,780
Можемо зауставити.

113
00:05:07,780 --> 00:05:10,561
Ми успешно завршен
бинарни претрага.

114
00:05:10,561 --> 00:05:11,060
У реду.

115
00:05:11,060 --> 00:05:13,930
Дакле, знамо овај алгоритам
ради ако је мета

116
00:05:13,930 --> 00:05:16,070
негде унутар низа.

117
00:05:16,070 --> 00:05:19,060
Да ли овај алгоритам радити ако
мета није у низу?

118
00:05:19,060 --> 00:05:20,810
Па, хајде да га покренете
опет, и овај пут,

119
00:05:20,810 --> 00:05:23,380
Погледајмо за елемент
16, који визуелно можемо да видимо

120
00:05:23,380 --> 00:05:25,620
не нигде не постоји у низу.

121
00:05:25,620 --> 00:05:27,110
>> Почетна тачка је поново 0.

122
00:05:27,110 --> 00:05:28,590
Крајња тачка је опет 14.

123
00:05:28,590 --> 00:05:32,490
То су индекси првог и
последњих елементи комплетног низа.

124
00:05:32,490 --> 00:05:36,057
И ми ћемо проћи кроз процес смо само
прошао кроз поново покушавају да пронађу 16,

125
00:05:36,057 --> 00:05:39,140
иако визуелно, већ можемо
рећи да неће бити тамо.

126
00:05:39,140 --> 00:05:43,450
Ми само желимо да се уверим да овај алгоритам
ће, у ствари, још увек раде у неки начин

127
00:05:43,450 --> 00:05:46,310
и не само нас остави
заглављен у бесконачну петљу.

128
00:05:46,310 --> 00:05:48,190
>> Дакле, шта је први корак?

129
00:05:48,190 --> 00:05:50,230
Израчунајте средиште
тренутне низа.

130
00:05:50,230 --> 00:05:52,790
Шта је средину
садашњег низа?

131
00:05:52,790 --> 00:05:54,410
Па, то је 7, зар не?

132
00:05:54,410 --> 00:05:57,560
14 Плус 0 подељено са 2 је 7.

133
00:05:57,560 --> 00:05:59,280
Да ли је 15 оно што тражите?

134
00:05:59,280 --> 00:05:59,780
Ne.

135
00:05:59,780 --> 00:06:02,930
То је прилично близу, али ми тражимо
за вредност незнатно већи од тога.

136
00:06:02,930 --> 00:06:06,310
>> Дакле, знамо да ће
бити нигде са леве стране 15.

137
00:06:06,310 --> 00:06:08,540
Циљ је већи од
оно што је у централном вредношћу.

138
00:06:08,540 --> 00:06:12,450
И тако смо поставили нову почетну тачку на
бити само на десној страни средини.

139
00:06:12,450 --> 00:06:16,130
Средину је тренутно 7, тако
Рецимо нови почетак поента је 8.

140
00:06:16,130 --> 00:06:18,130
И оно што сам ефективно
опет урадио је игнорисао

141
00:06:18,130 --> 00:06:21,150
читава леви половини низа.

142
00:06:21,150 --> 00:06:23,750
>> Сада смо поновити
обрађује још једном.

143
00:06:23,750 --> 00:06:24,910
Израчунајте нови средиште.

144
00:06:24,910 --> 00:06:29,350
8, плус 14 је 22, подељено са 2 је 11.

145
00:06:29,350 --> 00:06:31,060
Да ли је 23 оно што тражите?

146
00:06:31,060 --> 00:06:31,870
Нажалост нема.

147
00:06:31,870 --> 00:06:34,930
Тражимо вредности
то је мање од 23.

148
00:06:34,930 --> 00:06:37,850
И тако у овом случају, идемо
да промените крајњу тачку да буде само

149
00:06:37,850 --> 00:06:40,035
лево од тренутног вредношћу.

150
00:06:40,035 --> 00:06:43,440
Тренутни мидпоинт је 11, и
тако да ћемо поставити нову крајњу тачку

151
00:06:43,440 --> 00:06:46,980
за наредни пут кад одемо
кроз овај процес до 10.

152
00:06:46,980 --> 00:06:48,660
>> Опет, идемо кроз процес поново.

153
00:06:48,660 --> 00:06:49,640
Израчунајте средиште.

154
00:06:49,640 --> 00:06:53,100
8, плус 10 подељено са 2 је 9.

155
00:06:53,100 --> 00:06:54,750
Да ли је 19 оно што тражите?

156
00:06:54,750 --> 00:06:55,500
Нажалост нема.

157
00:06:55,500 --> 00:06:58,050
Још увек тражимо
број мање од тога.

158
00:06:58,050 --> 00:07:02,060
Дакле, ми ћемо променити крајња тачка овог пута
да буде само лево од средње вредности.

159
00:07:02,060 --> 00:07:05,532
Средину је тренутно 9,
тако да крајња тачка ће бити 8.

160
00:07:05,532 --> 00:07:07,920
И сада, ми смо само тражимо
при једној елемента низа.

161
00:07:07,920 --> 00:07:10,250
>> Шта је средиште овог низа?

162
00:07:10,250 --> 00:07:13,459
Па, почиње у 8, било
завршава у 8, средиште је 8.

163
00:07:13,459 --> 00:07:14,750
Да ли је то оно што тражите?

164
00:07:14,750 --> 00:07:16,339
Да ли у потрази за 17?

165
00:07:16,339 --> 00:07:17,380
Не, ми тражимо 16.

166
00:07:17,380 --> 00:07:20,160
Дакле, ако постоји у низу,
то мора да постоји негде

167
00:07:20,160 --> 00:07:21,935
на лево од места где тренутно смо.

168
00:07:21,935 --> 00:07:23,060
Па шта ћемо да радимо?

169
00:07:23,060 --> 00:07:26,610
Па, ми ћемо одредите крајњу тачку да буде само
лево од тренутног вредношћу.

170
00:07:26,610 --> 00:07:29,055
Тако ћемо промијенити крајњу тачку до 7.

171
00:07:29,055 --> 00:07:32,120
Да ли видите шта се управо
десило овде, иако?

172
00:07:32,120 --> 00:07:33,370
Погледајте овде сада.

173
00:07:33,370 --> 00:07:35,970
>> Старт је сада већи од краја.

174
00:07:35,970 --> 00:07:39,620
Ефикасно, два краја
наше низа су прешли,

175
00:07:39,620 --> 00:07:42,252
и почетна тачка је
сада након крајња тачка.

176
00:07:42,252 --> 00:07:43,960
Па, то не
никаквог смисла, зар не?

177
00:07:43,960 --> 00:07:47,960
Дакле, сада, оно што могу да кажем је да
имају под низ величине 0.

178
00:07:47,960 --> 00:07:50,110
А када смо стигли до
ова тачка, сада можемо

179
00:07:50,110 --> 00:07:53,940
гарантује да елемент 16
не постоји у низу,

180
00:07:53,940 --> 00:07:56,280
јер почетне тачке
и крајња тачка прешли.

181
00:07:56,280 --> 00:07:58,340
И тако да није ту.

182
00:07:58,340 --> 00:08:01,340
Сада, приметите да је ово благо
разликује од почетне тачке и на крају

183
00:08:01,340 --> 00:08:02,900
Поента је иста.

184
00:08:02,900 --> 00:08:05,030
Да смо били у потрази
за 17, она би морала

185
00:08:05,030 --> 00:08:08,870
био у низу, и почетне тачке
и крајња тачка тог ласт итерација

186
00:08:08,870 --> 00:08:11,820
пре те тачке прешли,
бисмо нашли 17 тамо.

187
00:08:11,820 --> 00:08:15,510
То је само када пређу да можемо
гарантује да елемент не

188
00:08:15,510 --> 00:08:17,180
постоје у низу.

189
00:08:17,180 --> 00:08:20,260
>> Дакле, хајде да узмемо много мање
кораци од линеарног потрази.

190
00:08:20,260 --> 00:08:23,250
У најгорем сценарију, имали смо
да раздвојимо листу н елемената

191
00:08:23,250 --> 00:08:27,770
у више наврата на пола да пронађу циљ,
или зато што је мета елемента

192
00:08:27,770 --> 00:08:33,110
ће бити негде у последња
подела, или не постоји уопште.

193
00:08:33,110 --> 00:08:37,830
Дакле, у најгорем случају, морамо да
разишли су арраи-- знаш?

194
00:08:37,830 --> 00:08:40,510
Се од н пута; ми
морати да смање проблем

195
00:08:40,510 --> 00:08:42,610
за пола одређеном броју пута.

196
00:08:42,610 --> 00:08:45,160
Тај број пута је лог н.

197
00:08:45,160 --> 00:08:46,510
>> Шта је најбољи сценарио?

198
00:08:46,510 --> 00:08:48,899
Па, први пут смо
израчунати средиште,

199
00:08:48,899 --> 00:08:50,190
нађемо оно што тражимо.

200
00:08:50,190 --> 00:08:52,150
У свим претходни
примери бинарни потрази

201
00:08:52,150 --> 00:08:55,489
смо управо прошли кроз, ако смо имали
Тражио елемента 15,

202
00:08:55,489 --> 00:08:57,030
бисмо открили да одмах.

203
00:08:57,030 --> 00:08:58,321
То је на самом почетку.

204
00:08:58,321 --> 00:09:01,200
То је био средиште
први покушај делићу

205
00:09:01,200 --> 00:09:03,950
од поделе у бинарном потрази.

206
00:09:03,950 --> 00:09:06,350
>> И тако у најгорем
случај, бинарни претрага води

207
00:09:06,350 --> 00:09:11,580
у лог Н, који је супстанцијално бољи
од линеарног потрази, у најгорем случају.

208
00:09:11,580 --> 00:09:16,210
У најбољем случају, бинари
претрага ради у омега 1.

209
00:09:16,210 --> 00:09:18,990
Дакле, бинарна претрага је много
боље него линеарно претрагу,

210
00:09:18,990 --> 00:09:23,270
али морате да се баве процесом
сортирање своју низ прије него што можете

211
00:09:23,270 --> 00:09:26,140
искористи моћ бинарне претраге.

212
00:09:26,140 --> 00:09:27,130
>> Ја сам Доуг Лојд.

213
00:09:27,130 --> 00:09:29,470
Ово је ЦС 50.

214
00:09:29,470 --> 00:09:31,070