二分搜的概念

終極密碼

終極密碼的規則如下 : 在規定的範圍內，你每一輪都會猜一個數字，然後你的對手會告訴你這個數字比答案大還是小，重複以上步驟直到猜中正確的數字。

關於這個遊戲，有什麼策略能夠在最短的時間內找到正確答案呢 ?

二分搜

此時，我們想到一個很聰明的策略，這個策略基於一個關鍵的想法：每次猜測都要盡量排除一半的可能性。

那麼要如何做到每次都排除一半呢 ?

這裡有一個例子來說明這個概念（假設答案在 1 ~ 100 之間）：

1. 首先，你猜 50。如果答案比 50 大，你知道答案只可能在 51 到 100 之間，因為如果答案在 1 到 49 之間，你的對手會告訴你它比 50 小。

2. 如果答案比 50 小，你知道答案只可能在 1 到 49 之間。這樣一來，你每次都能排除一半的可能性。

3. 接下來，你再猜測 25（如果答案比 50 大）或者 75（如果答案比50 小）。

4. 以此類推，每次你都會縮小搜索範圍一半，直到你找到答案。

這就是二分搜索的核心思想：每次搜尋後，你都會將搜索範圍縮小一半，直到最終找到答案。這種方法非常高效率，尤其是在搜索範圍很大的情況下，可以極大地減少搜索所需的次數。

二分搜的使用條件

當資料沒有 單調性 的時候，二分搜無法正常地運作。原因在於二分搜的核心思想是通過比較目標值和數據中間元素的大小關係來決定搜索方向，進而將搜索範圍一分為二。如果數據是沒有單調性，那麼無法確定中間元素的大小關係，導致無法有效地縮小搜索範圍，最終導致算法失效。

因此，在使用二分搜之前，我們通常需要先將數據進行排序，以確保數據是有單調性的，從而保證二分搜索算法的正確性和效率。