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
>> DOUG 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
>> 让我们想象这样好不好？

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
这个次数是日志ñ。

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