>> [音樂播放]
>> DOUG LLOYD：好吧。
所以二進制搜索是一個 算法，我們可以用
找到一個陣列中的元素。
與線性搜索，它需要一個 特殊情況事先滿足，
但它是如此，如果更有效 該條件是，實際上，滿足。
>> 那麼，有什麼想法嗎？
這是分而治之。
我們要減少的大小 半每次由搜索區域
為了找到一個目標數。
這是該條件 進場時，雖然。
我們只能充分利用的力量 元素的消除半
連看都沒看一眼 他們如果數組排序。
>> 如果它是一個完整的組合起來， 我們不能只是伸出手
丟棄一半的元件，因為 我們不知道我們正在拋棄。
但是，如果該數組排序， 我們可以做到這一點，因為我們
知道這一切的 在那裡，我們目前還剩下
必須比低 價值我們目前在。
所有的一切都為 正確的我們在哪裡
必須大於該值 我們目前正在觀察。
>> 那麼什麼是偽 對於二進制搜索的步驟？
我們重複這個過程，直到 陣列或者，當我們繼續完成，
子陣列，小件 原來的數組，是大小為0。
計算中點 當前子陣列。
>> 如果你正在尋找的價值 在該陣列的該元素，停止。
你發現了它。
這是偉大的。
否則，如果目標是 小於什麼在中間，
因此，如果該值，我們正在尋找 對於比我們所看到的低，
再次重複此過程，但 改變結束點，而不是
被原 完成全陣列，
要到左邊 在那裡，我們只是看著。
>> 我們知道，中間的太高， 或目標是小於中間，
因此它必須存在，如果它 在所有存在於所述陣列，
某處中點的左側。
因此，我們將設置陣列 位置到左邊
的中點作為新的終點。
相反，如果所述目標是 大於什麼在中間，
我們做同樣的 過程，而是我們
更改開始點為 只是為了中點的右
我們剛剛計算。
然後，我們再開始這個過程。
>> 讓我們想像這樣好不好？
所以這是一個很多事情，並就到這裡， 但這裡的15個元素的數組。
而我們將要被跟踪 對很多更多的東西這個時候。
因此，在線性搜索，我們 只是關心的目標。
但是這一次，我們要 關心我們在哪裡
在那裡開始尋找， 在我們停止尋找，
什麼是中點 目前陣。
所以在這裡，我們一起去二進制搜索。
我們非常好走，對不對？
我只是要放下 下面在這裡一組指標。
這基本上是哪些因素 數組的，我們正在談論。
隨著線性搜索，我們 關心，因為我們
需要知道多少 我們迭代的元素，
但我們並不真正關心什麼 元素，我們目前正在觀察。
在二進制搜索，我們做的。
所以這些只是 有作為一個小導遊。
>> 因此，我們可以開始了吧？
好了，不完全是。
還記得我說的 關於二進​​制搜索？
我們不能上做 排序的數組否則，
我們不低保 某些元素或值是不
被意外 丟棄的時候，我們剛剛
決定忽略一半陣列。
>> 因此，與二進制搜索第一步 是你必須有一個排序的數組。
你可以使用任何排序 我們已經討論過的算法
讓你到那個位置。
所以，現在，我們正處在一個位置， 我們可以執行二進制搜索。
>> 因此，讓我們重複這個過程 一步一步，並保持
軌道發生了什麼，因為我們去。
因此，首先我們要做的是計算 當前陣列的中點。
好了，我們會說我們是，第一 總之，尋找值19。
我們正試圖找到19號。
這樣做的第一個元素 陣列位於指數為零，
並在此最後一個元素 陣列位於指數14。
因此，我們會打電話給那些開始和結束。
>> 因此，我們計算出中點按 加0加上14除以2;
非常簡單的中點。
我們可以說， 中點是現在7。
所以是15，我們在找什麼？
不，不是這樣的。
我們正在尋找19。
但我們知道，19大 比我們發現在中間。
>> 所以我們所能做的就是 更改起點
是剛剛的權 中點，並再次重複上述過程。
而當我們這樣做，我們現在說的 新的起點就是數組位置8。
我們已經有效地完成工作是 無視一切的15次左右。
我們已經消除了一半 這個問題，現在，
而不必搜索 在我們的數組超過15元，
我們只需要搜索超過7。
因此，8是新的起點。
圖14是仍然終點。
>> 而現在，我們過這一次。
我們計算出新的中點。
8加14是22，2是11分。
這是我們在尋找什麼？
不，不是這樣的。
我們正在尋找一個值的 不是我們剛剛發現少了。
所以，我們要重複 再次的過程。
我們要改變終點 只是為了中點的左側。
因此，新的終點變成10。
而現在，這是唯一的一部分 數組我們必須通過排序。
所以，我們現在已經淘汰 12的15元素。
我們知道，如果19 存在陣列中，它
必須存在的元素之間的某處 號8和元件數目10。
>> 因此，我們再次計算新的中點。
8加10是18，2是9分。
在這種情況下，一看， 目標是在中間。
我們發現我們在尋找什麼。
我們可以停止。
我們成功完成 二進制搜索。
好的。
因此，我們知道這個算法 工作如果目標是
某處陣列的內部。
請問這種算法的工作，如果 目標不是陣列中？
好了，讓我們開始這 再次，這一次，
讓我們來看看該元素 16，這在視覺上可以看到
不會在陣列中任何地方存在。
>> 再次開始點是0。
再次終點是14。
這些是第一個的索引和 整個陣列的最後一個元素。
而我們將要經歷的過程，我們只 經歷了一遍，試圖找到16，
儘管在視覺上，我們已經可以 告訴大家，它不會在那裡。
我們只是想確保這個算法 將，實際上，仍然工作在某些方面
而不是只留給我們 陷入無限循環。
>> 那麼，有什麼步驟第一？
計算中點 目前陣。
什麼是中點 目前陣？
嗯，這是7，對不對？
14加0除以2是7。
15，我們在尋找什麼？
第
這是相當接近，但我們正在尋找 為一個值比稍大。
>> 因此，我們知道，這將 無處15的左側。
目標是大於 什麼是在中點。
因此，我們設定了新的起點 只是到中間的右邊。
中點目前是7，所以 讓我們說，新的起點為8。
而我們有效地已經 再行被忽略
該陣列的整個左半部。
>> 現在，我們重複 處理一次。
計算新的中點。
8加14是22，2是11分。
23，我們在尋找什麼？
不幸的是，沒有。
我們正在尋找一個值 小於23。
所以在這種情況下，我們將 改變結束點是公正
到當前中點的左側。
當前中點為11，並且 因此，我們將設置新的終點
下一次我們去 通過這一過程，以10。
>> 同樣，我們再次經歷的過程。
計算的中點。
8加10除以2是9。
19，我們在尋找什麼？
不幸的是，沒有。
我們還在尋找 若干少於。
所以我們這次改變終點 是公正的中點的左側。
中點目前是9， 因此終點將是8。
而現在，我們只是在尋找 在一個單一的元件陣列。
>> 這是什麼陣的中點？
那麼，它開始於8，它 結束於圖8中，中點是8。
那是我們正在尋找什麼？
我們尋找17？
不，我們正在尋找的16。
因此，如果它存在於數組中， 它必須存在的地方
到的，其中我們當前有左側。
那麼，我們該怎麼辦？
好了，我們將設置終點是公正 到當前中點的左側。
因此，我們將終點更改為7。
你看一下剛才 這裡發生了，有關係嗎？
查一查這裡。
>> 開始是現在大於結束。
有效地，兩端 我們的陣列已經越過，
與開始點是 現在後的終點。
好了，不 任何意義，不是嗎？
所以，現在，我們可以說的是，我們 有大小為0的子陣列。
而一旦我們得到了以 這一點，我們現在可以
保證元件16 在陣列中不存在，
因為起點 和終點越過。
所以它的不存在。
現在，請注意，這是略微 比開始點和結束不同
點是相同的。
如果我們一直在尋找 為17，這將有
過陣列，並且起始點在 並結束了最後一次迭代點
這些交叉點之前， 我們會發現17在那裡。
只有當他們越過我們可以 保證元件不
存在陣列中。
>> 因此，讓我們少了很多 步驟不是線性搜索。
在最壞的情況下，我們有 分裂n個元素的列表
多次在半找到目標， 要么是因為目標元素
將在最後的某處 師，或不存在，在所有。
因此，在最壞的情況下，我們不得不 分裂的array--你知道嗎？
n次記錄;我們 不得不削減問題
在半一定的次數。
這個次數是日誌ñ。
>> 什麼是最好的情況？
好了，我們第一次 計算的中點，
我們發現，我們所要尋找的。
在所有前面的 二進制搜索示例
我們剛剛走了過來，如果我們有 一直在尋找的元素15，
我們會立即發現。
這是在開始。
這是中點 在一個分裂的第一次嘗試
在二進制搜索一個部門。
>> 因此在最壞的 情況下，二進制搜索運行
在日誌n，這個基本上更好 比線性搜索，在最壞的情況下。
在最好的情況下，二進制 搜索運行在1歐米加。
所以二進制搜索是一個很大 比線性尋找更好的，
但你必須處理的過程 之前，你可以先整理你的數組
利用二分搜索的功率。
>> 我是道格·勞埃德。
這是CS 50。