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
>> Даг LLOYD: Во ред.

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
>> Значи она што е pseudocode
чекори за бинарни пребарување?

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
Бр

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
Во најлош случај, имавме
да се подели до листа на n елементи

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
Така што во најлош случај, ние треба да се
подели на array-- знаеш?

194
00:08:37,830 --> 00:08:40,510
Дневник на n пати; ние
мора да го намали проблемот

195
00:08:40,510 --> 00:08:42,610
половина на одреден број на пати.

196
00:08:42,610 --> 00:08:45,160
Дека бројот на пати се најавите n.

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
во дневникот n, што е значително подобро
од линеарно пребарување, во најлош случај.

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