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
>> Така че това, което е Псевдокод
стъпки за двоично търсене?

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
>> Нека да визуализираме това, OK?

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
В най-лошия случай, имахме
да се раздели на списък на наш елементи

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
Вход на п пъти; ние
трябва да намалят проблема

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
Вход 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
Това е CS 50.

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