一種針對有序數(shù)據(jù)集合的查找算法：二分查找（Binary Search）算法，也叫折半查找算法。

二分查找針對的是一個有序的數(shù)據(jù)集合，查找思想有點類似分治思想。每次都通過跟區(qū)間的中間元素對比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間被縮小為 0。

驚人的查找速度 O(logn)

我們假設數(shù)據(jù)大小是 n，每次查找后數(shù)據(jù)都會縮小為原來的一半，也就是會除以 2。最壞情況下，直到查找區(qū)間被縮小為空，才停止。

可以看出來，這是一個等比數(shù)列。其中 n/2k=1 時，k 的值就是總共縮小的次數(shù)。而每一次縮小操作只涉及兩個數(shù)據(jù)的大小比較，所以，經(jīng)過了 k 次區(qū)間縮小操作，時間復雜度就是 O(k)。通過 n/2k=1，我們可以求得 ，所以時間復雜度就是 O(logn)。

除了二分查找，后面還會遇到的 堆、二叉樹的操作，它們時間復雜度也是 O(logn)。這里就再深入地講講 O(logn) 這種對數(shù)時間復雜度。這是一種極其高效的時間復雜度，有的時候甚至比時間復雜度是常量級O(1) 的算法還要高效。為什么這么說呢？

因為 logn 是一個非常“恐怖”的數(shù)量級，即便 n 非常非常大，對應的 logn 也很小。比如 n 等于 2 的 32 次方，這個數(shù)很大了吧？大約是 42 億。也就是說，如果我們在 42 億個數(shù)據(jù)中用二分查找一個數(shù)據(jù)，最多需要比較 32 次。

我們前面講過，用大 O 標記法表示時間復雜度的時候，會省略掉常數(shù)、系數(shù)和低階。對于常量級時間復雜度的算法來說，O(1) 有可能表示的是一個非常大的常量值，比如 O(1000)、O(10000)。所以，常量級時間復雜度的算法有時候可能還沒有O(logn) 的算法執(zhí)行效率高。

反過來，對數(shù)對應的就是指數(shù)。指數(shù)時間復雜度的算法在大規(guī)模數(shù)據(jù)面前是無效的。

二分查找的遞歸與非遞歸實現(xiàn)

簡單的二分查找并不難寫，下一節(jié)，我們會講到二分查找的變體問題，那才是真正燒腦的。我們來看如何來寫最簡單的二分查找。

最簡單的情況就是有序數(shù)組中不存在重復元素，我們在其中用二分查找值等于給定值的數(shù)據(jù)。

稍微解釋一下思路，low、high、mid 都是指數(shù)組下標，其中 low 和 high 表示當前查找的區(qū)間范圍，初始 low=0， high=n-1。mid 表示 [low, high] 的中間位置。我們通過對比 a[mid] 與 value 的大小，來更新接下來要查找的區(qū)間范圍，直到找到或者區(qū)間縮小為 0，就退出。

著重強調一下容易出錯的 3 個地方。

1. 循環(huán)退出條件

注意是 low<=high，而不是 low<high

2. mid 的取值

mid=(low+high)/2 這種寫法是有問題的。因為如果 low 和 high 比較大的話，兩者之和就有可能會溢出。改進的方法是將 mid 的計算方式寫成 low+(high-low)/2。更進一步，如果要將性能優(yōu)化到極致的話，我們可以將這里的除以 2 操作轉化成位運算 low+((high-low)>>1)。因為相比除法運算來說，計算機處理位運算要快得多。

3. low 和 high 的更新

low=mid+1，high=mid-1。注意這里的 +1 和 -1，如果直接寫成 low=mid 或者 high=mid，就可能會發(fā)生死循環(huán)。比如，當 high=3，low=3 時，如果 a[3] 不等于value，就會導致一直循環(huán)不退出。

簡單二分查找的相關代碼請移步 Leooel 的博客。

二分查找應用場景的局限性

二分查找的時間復雜度是 O(logn)，查找數(shù)據(jù)的效率非常高。不過，并不是什么情況下都可以用二分查找，它的應用場景是有很大局限性的。那什么情況下適合用二分查找，什么情況下不適合呢？

• 首先，二分查找依賴的是順序表結構，簡單點說就是數(shù)組。

二分查找只能用在數(shù)據(jù)是通過順序表來存儲的數(shù)據(jù)結構上。如果你的數(shù)據(jù)是通過其他數(shù)據(jù)結構存儲的，則無法應用二分查找。

• 其次，二分查找針對的是有序數(shù)據(jù)。

二分查找對這一點的要求比較苛刻，數(shù)據(jù)必須是有序的。如果數(shù)據(jù)沒有序，我們需要先排序。前面章節(jié)里我們講到，排序的時間復雜度最低是 O(nlogn)。所以，如果我們針對的是一組靜態(tài)的數(shù)據(jù)，沒有頻繁地插入、刪除，我們可以進行一次排序，多次二分查找。這樣排序的成本可被均攤，二分查找的邊際成本就會比較低。

但是，如果我們的數(shù)據(jù)集合有頻繁的插入和刪除操作，要想用二分查找，要么每次插入、刪除操作之后保證數(shù)據(jù)仍然有序，要么在每次二分查找之前都先進行排序。針對這種動態(tài)數(shù)據(jù)集合，無論哪種方法，維護有序的成本都是很高的。

所以，二分查找只能用在插入、刪除操作不頻繁，一次排序多次查找的場景中。針對動態(tài)變化的數(shù)據(jù)集合，二分查找將不再適用。那針對動態(tài)數(shù)據(jù)集合，如何在其中快速查找某個數(shù)據(jù)呢？二叉樹那節(jié)會講到。

• 再次，數(shù)據(jù)量太小不適合二分查找。

數(shù)據(jù)量很小時，順序遍歷就足夠了，完全沒有必要用二分查找。只有數(shù)據(jù)量比較大的時候，二分查找的優(yōu)勢才會比較明顯。

有一個例外。如果數(shù)據(jù)之間的比較操作非常耗時，不管數(shù)據(jù)量大小，都推薦使用二分查找。比如，數(shù)組中存儲的都是長度超過 300 的字符串，如此長的兩個字符串之間比對大小，就會非常耗時。我們需要盡可能地減少比較次數(shù)，而比較次數(shù)的減少會大大提高性能，這個時候二分查找就比順序遍歷更有優(yōu)勢。

• 最后，數(shù)據(jù)量太大也不適合二分查找。

二分查找的底層需要依賴數(shù)組這種數(shù)據(jù)結構，而數(shù)組為了支持隨機訪問的特性，要求內存空間連續(xù)，對內存的要求比較苛刻。比如，我們有 1GB 大小的數(shù)據(jù)，如果希望用數(shù)組來存儲，那就需要 1GB 的連續(xù)內存空間。

注意這里的“連續(xù)”二字，也就是說，即便有 2GB 的內存空間剩余，但是如果這剩余的 2GB 內存空間都是零散的，沒有連續(xù)的 1GB 大小的內存空間，那照樣無法申請一個 1GB 大小的內存空間，那照樣無法申請一個 1GB 大小的數(shù)組。而我們的二分查找是作用在數(shù)組這種數(shù)據(jù)結構之上的，所以太大的數(shù)據(jù)用數(shù)組存儲就比較吃力了，也就不能用二分查找了。

開篇解答

如何在 1000 萬個整數(shù)中快速查找某個整數(shù)？內存限制是 100MB，每個數(shù)據(jù)大小是 8 字節(jié)。

最簡單的辦法就是將數(shù)據(jù)存儲在數(shù)組中，內存占用差不多是 80M，符合內存的限制。借助今天講的內容，我們可以先對這 1000 萬數(shù)據(jù)從小到大排序，然后再利用二分查找算法，就可以快速地查找想要的數(shù)據(jù)了。

雖然大部分情況下，用二分查找可以解決的問題，用散列表、二叉樹都可以解決。后面會講，不管是散列表還是二叉樹，都會需要比較多的額外的內存空間。而這里是有內存限制的。

而二分查找底層依賴的是數(shù)組，除了數(shù)據(jù)本身之外，不需要額外存儲其他信息，是最省內存空間的存儲方式，所以剛好能在限定的內存大小下解決這個問題。

小結

二分查找，一種針對有序數(shù)據(jù)的高效查找算法，它的時間復雜度是 O(logn)。

二分查找雖然性能比較優(yōu)秀，但應用場景也比較有限。底層必須依賴數(shù)組，并且還要求數(shù)據(jù)是有序的。對于較小規(guī)模的數(shù)據(jù)查找，我們直接使用順序遍歷就可以了，二分查找的優(yōu)勢并不明顯。二分查找更適合處理靜態(tài)數(shù)據(jù)，也就是沒有頻繁的數(shù)據(jù)插入、刪除操作。

課后思考

1. 如何編程實現(xiàn)“求一個數(shù)的平方根”？要求精確到小數(shù)點后 6 位。

2. 我剛才說了，如果數(shù)據(jù)使用鏈表存儲，二分查找的時間復雜就會變得很高，那查找的時間復雜度究竟是多少呢？如果你自己推導一下，你就會深刻地認識到，為何我們會選擇用數(shù)組而不是鏈表來實現(xiàn)二分查找了。