[音樂播放] 

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。