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