二分查找（上）：如何用最省內(nèi)存的方式實(shí)現(xiàn)快速查找功能秉继？
今天我們講一種針對有序數(shù)據(jù)集合的查找算法：二分查找（Binary Search）算法，也叫折半查找算法泽铛。二分查找的思想非常簡單尚辑，很多非計(jì)算機(jī)專業(yè)的同學(xué)很容易就能理解，但是看似越簡單的東西往往越難掌握好盔腔，想要靈活應(yīng)用就更加困難杠茬。
老規(guī)矩，我們還是來看一道思考題弛随。
假設(shè)我們有 1000 萬個整數(shù)數(shù)據(jù)瓢喉，每個數(shù)據(jù)占 8 個字節(jié)，如何設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法舀透，快速判斷某個整數(shù)是否出現(xiàn)在這 1000 萬數(shù)據(jù)中栓票？ 我們希望這個功能不要占用太多的內(nèi)存空間，最多不要超過 100MB愕够，你會怎么做呢走贪？帶著這個問題，讓我們進(jìn)入今天的內(nèi)容吧惑芭！
無處不在的二分思想
二分查找是一種非常簡單易懂的快速查找算法坠狡，生活中到處可見。比如說遂跟，我們現(xiàn)在來做一個猜字游戲途蒋。我隨機(jī)寫一個 0 到 99 之間的數(shù)字绪商，然后你來猜我寫的是什么。猜的過程中，你每猜一次壁肋，我就會告訴你猜的大了還是小了，直到猜中為止驱显。你來想想拆祈，如何快速猜中我寫的數(shù)字呢？
假設(shè)我寫的數(shù)字是 23究飞，你可以按照下面的步驟來試一試置谦。（如果猜測范圍的數(shù)字有偶數(shù)個堂鲤，中間數(shù)有兩個，就選擇較小的那個媒峡。）
7 次就猜出來了瘟栖，是不是很快？這個例子用的就是二分思想谅阿，按照這個思想半哟，即便我讓你猜的是 0 到 999 的數(shù)字，最多也只要 10 次就能猜中签餐。不信的話寓涨，你可以試一試。
這是一個生活中的例子氯檐，我們現(xiàn)在回到實(shí)際的開發(fā)場景中戒良。假設(shè)有 1000 條訂單數(shù)據(jù)，已經(jīng)按照訂單金額從小到大排序冠摄，每個訂單金額都不同糯崎，并且最小單位是元。我們現(xiàn)在想知道是否存在金額等于 19 元的訂單河泳。如果存在沃呢，則返回訂單數(shù)據(jù)，如果不存在則返回 null拆挥。
最簡單的辦法當(dāng)然是從第一個訂單開始薄霜，一個一個遍歷這 1000 個訂單，直到找到金額等于 19 元的訂單為止纸兔。但這樣查找會比較慢黄锤，最壞情況下，可能要遍歷完這 1000 條記錄才能找到食拜。那用二分查找能不能更快速地解決呢鸵熟？
為了方便講解，我們假設(shè)只有 10 個訂單负甸，訂單金額分別是：8流强，11，19呻待，23打月，27，33蚕捉，45奏篙，55，67，98秘通。
還是利用二分思想为严，每次都與區(qū)間的中間數(shù)據(jù)比對大小，縮小查找區(qū)間的范圍肺稀。為了更加直觀第股，我畫了一張查找過程的圖。其中话原，low 和 high 表示待查找區(qū)間的下標(biāo)夕吻，mid 表示待查找區(qū)間的中間元素下標(biāo)。
看懂這兩個例子繁仁，你現(xiàn)在對二分的思想應(yīng)該掌握得妥妥的了涉馅。我這里稍微總結(jié)升華一下，二分查找針對的是一個有序的數(shù)據(jù)集合黄虱，查找思想有點(diǎn)類似分治思想控漠。每次都通過跟區(qū)間的中間元素對比，將待查找的區(qū)間縮小為之前的一半悬钳，直到找到要查找的元素，或者區(qū)間被縮小為 0偶翅。
O(logn) 驚人的查找速度
二分查找是一種非常高效的查找算法默勾，高效到什么程度呢？我們來分析一下它的時間復(fù)雜度聚谁。
我們假設(shè)數(shù)據(jù)大小是 n母剥，每次查找后數(shù)據(jù)都會縮小為原來的一半，也就是會除以 2形导。最壞情況下环疼，直到查找區(qū)間被縮小為空，才停止朵耕。
可以看出來炫隶，這是一個等比數(shù)列。其中 n/2k=1 時阎曹，k 的值就是總共縮小的次數(shù)伪阶。而每一次縮小操作只涉及兩個數(shù)據(jù)的大小比較，所以处嫌，經(jīng)過了 k 次區(qū)間縮小操作栅贴，時間復(fù)雜度就是 O(k)。通過 熏迹，我們可以求得
檐薯，所以時間復(fù)雜度就是 O(logn)。
二分查找是我們目前為止遇到的第一個時間復(fù)雜度為 O(logn) 的算法注暗。后面章節(jié)我們還會講堆坛缕、二叉樹的操作等等墓猎，它們的時間復(fù)雜度也是 O(logn)。我這里就再深入地講講 O(logn) 這種對數(shù)時間復(fù)雜度祷膳。這是一種極其高效的時間復(fù)雜度陶衅，有的時候甚至比時間復(fù)雜度是常量級 O(1) 的算法還要高效。為什么這么說呢直晨？
因?yàn)?logn 是一個非巢缶“恐怖”的數(shù)量級，即便 n 非常非常大勇皇，對應(yīng)的 logn 也很小罩句。比如 n 等于 2 的 32 次方，這個數(shù)很大了吧敛摘？大約是 42 億门烂。也就是說，如果我們在 42 億個數(shù)據(jù)中用二分查找一個數(shù)據(jù)兄淫，最多需要比較 32 次屯远。
我們前面講過，用大 O 標(biāo)記法表示時間復(fù)雜度的時候捕虽，會省略掉常數(shù)慨丐、系數(shù)和低階。對于常量級時間復(fù)雜度的算法來說泄私，O(1) 有可能表示的是一個非常大的常量值房揭，比如 O(1000)、O(10000)晌端。所以捅暴，常量級時間復(fù)雜度的算法有時候可能還沒有 O(logn) 的算法執(zhí)行效率高。
反過來咧纠，對數(shù)對應(yīng)的就是指數(shù)蓬痒。有一個非常著名的“阿基米德與國王下棋的故事”，你可以自行搜索一下漆羔，感受一下指數(shù)的“恐怖”乳幸。這也是為什么我們說，指數(shù)時間復(fù)雜度的算法在大規(guī)模數(shù)據(jù)面前是無效的钧椰。
二分查找的遞歸與非遞歸實(shí)現(xiàn)
實(shí)際上粹断，簡單的二分查找并不難寫，注意我這里的“簡單”二字嫡霞。下一節(jié)瓶埋，我們會講到二分查找的變體問題，那才是真正燒腦的。今天养筒，我們來看如何來寫最簡單的二分查找曾撤。
最簡單的情況就是有序數(shù)組中不存在重復(fù)元素，我們在其中用二分查找值等于給定值的數(shù)據(jù)晕粪。我用 Java 代碼實(shí)現(xiàn)了一個最簡單的二分查找算法挤悉。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
這個代碼我稍微解釋一下，low巫湘、high装悲、mid 都是指數(shù)組下標(biāo)，其中 low 和 high 表示當(dāng)前查找的區(qū)間范圍尚氛，初始 low=0诀诊， high=n-1。mid 表示 [low, high] 的中間位置阅嘶。我們通過對比 a[mid] 與 value 的大小属瓣，來更新接下來要查找的區(qū)間范圍，直到找到或者區(qū)間縮小為 0讯柔，就退出抡蛙。如果你有一些編程基礎(chǔ)，看懂這些應(yīng)該不成問題』昶現(xiàn)在粗截，我就著重強(qiáng)調(diào)一下容易出錯的 3 個地方。
- 循環(huán)退出條件
注意是 low<=high极祸，而不是 low<high。
2.mid 的取值
實(shí)際上怠晴，mid=(low+high)/2 這種寫法是有問題的遥金。因?yàn)槿绻?low 和 high 比較大的話，兩者之和就有可能會溢出蒜田。改進(jìn)的方法是將 mid 的計(jì)算方式寫成 low+(high-low)/2稿械。更進(jìn)一步，如果要將性能優(yōu)化到極致的話冲粤，我們可以將這里的除以 2 操作轉(zhuǎn)化成位運(yùn)算 low+((high-low)>>1)美莫。因?yàn)橄啾瘸ㄟ\(yùn)算來說，計(jì)算機(jī)處理位運(yùn)算要快得多梯捕。
3.low 和 high 的更新
low=mid+1厢呵，high=mid-1。注意這里的 +1 和 -1傀顾，如果直接寫成 low=mid 或者 high=mid襟铭，就可能會發(fā)生死循環(huán)。比如，當(dāng) high=3寒砖，low=3 時赐劣，如果 a[3] 不等于 value，就會導(dǎo)致一直循環(huán)不退出哩都。
如果你留意我剛講的這三點(diǎn)魁兼，我想一個簡單的二分查找你已經(jīng)可以實(shí)現(xiàn)了。實(shí)際上漠嵌，二分查找除了用循環(huán)來實(shí)現(xiàn)咐汞，還可以用遞歸來實(shí)現(xiàn)，過程也非常簡單献雅。
我用 Java 語言實(shí)現(xiàn)了一下這個過程碉考，正好你可以借此機(jī)會回顧一下寫遞歸代碼的技巧
// 二分查找的遞歸實(shí)現(xiàn)
//val是要查找的數(shù)字，n為數(shù)組的長度挺身，a為要查找的數(shù)組
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return bsearchInternally(a, mid+1, high, value);
} else {
return bsearchInternally(a, low, mid-1, value);
}
}
二分查找應(yīng)用場景的局限性
前面我們分析過侯谁，二分查找的時間復(fù)雜度是 O(logn)，查找數(shù)據(jù)的效率非常高章钾。不過墙贱，并不是什么情況下都可以用二分查找，它的應(yīng)用場景是有很大局限性的贱傀。那什么情況下適合用二分查找惨撇，什么情況下不適合呢？
首先府寒，二分查找依賴的是順序表結(jié)構(gòu)魁衙，簡單點(diǎn)說就是數(shù)組。
那二分查找能否依賴其他數(shù)據(jù)結(jié)構(gòu)呢株搔？比如鏈表剖淀。答案是不可以的，主要原因是二分查找算法需要按照下標(biāo)隨機(jī)訪問元素纤房。我們在數(shù)組和鏈表那兩節(jié)講過纵隔，數(shù)組按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的時間復(fù)雜度是 O(1)，而鏈表隨機(jī)訪問的時間復(fù)雜度是 O(n)炮姨。所以捌刮，如果數(shù)據(jù)使用鏈表存儲，二分查找的時間復(fù)雜就會變得很高舒岸。
二分查找只能用在數(shù)據(jù)是通過順序表來存儲的數(shù)據(jù)結(jié)構(gòu)上绅作。如果你的數(shù)據(jù)是通過其他數(shù)據(jù)結(jié)構(gòu)存儲的，則無法應(yīng)用二分查找蛾派。
其次棚蓄，二分查找針對的是有序數(shù)據(jù)堕扶。
二分查找對這一點(diǎn)的要求比較苛刻，數(shù)據(jù)必須是有序的梭依。如果數(shù)據(jù)沒有序稍算，我們需要先排序。前面章節(jié)里我們講到役拴，排序的時間復(fù)雜度最低是 O(nlogn)糊探。所以，如果我們針對的是一組靜態(tài)的數(shù)據(jù)河闰，沒有頻繁地插入科平、刪除，我們可以進(jìn)行一次排序姜性，多次二分查找瞪慧。這樣排序的成本可被均攤，二分查找的邊際成本就會比較低部念。
但是弃酌，如果我們的數(shù)據(jù)集合有頻繁的插入和刪除操作，要想用二分查找儡炼，要么每次插入妓湘、刪除操作之后保證數(shù)據(jù)仍然有序，要么在每次二分查找之前都先進(jìn)行排序乌询。針對這種動態(tài)數(shù)據(jù)集合榜贴，無論哪種方法，維護(hù)有序的成本都是很高的妹田。
所以唬党，二分查找只能用在插入、刪除操作不頻繁鬼佣，一次排序多次查找的場景中驶拱。針對動態(tài)變化的數(shù)據(jù)集合，二分查找將不再適用沮趣。那針對動態(tài)數(shù)據(jù)集合屯烦，如何在其中快速查找某個數(shù)據(jù)呢坷随？別急房铭，等到二叉樹那一節(jié)我會詳細(xì)講。
再次温眉，數(shù)據(jù)量太小不適合二分查找缸匪。
如果要處理的數(shù)據(jù)量很小，完全沒有必要用二分查找类溢，順序遍歷就足夠了凌蔬。比如我們在一個大小為 10 的數(shù)組中查找一個元素露懒，不管用二分查找還是順序遍歷，查找速度都差不多砂心。只有數(shù)據(jù)量比較大的時候懈词，二分查找的優(yōu)勢才會比較明顯。
不過辩诞，這里有一個例外坎弯。如果數(shù)據(jù)之間的比較操作非常耗時，不管數(shù)據(jù)量大小译暂，我都推薦使用二分查找抠忘。比如，數(shù)組中存儲的都是長度超過 300 的字符串外永，如此長的兩個字符串之間比對大小崎脉，就會非常耗時。我們需要盡可能地減少比較次數(shù)伯顶，而比較次數(shù)的減少會大大提高性能囚灼，這個時候二分查找就比順序遍歷更有優(yōu)勢。
最后砾淌，數(shù)據(jù)量太大也不適合二分查找啦撮。
二分查找的底層需要依賴數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，而數(shù)組為了支持隨機(jī)訪問的特性汪厨，要求內(nèi)存空間連續(xù)赃春，對內(nèi)存的要求比較苛刻。比如劫乱，我們有 1GB 大小的數(shù)據(jù)织中，如果希望用數(shù)組來存儲，那就需要 1GB 的連續(xù)內(nèi)存空間衷戈。
注意這里的“連續(xù)”二字狭吼，也就是說，即便有 2GB 的內(nèi)存空間剩余殖妇，但是如果這剩余的 2GB 內(nèi)存空間都是零散的刁笙，沒有連續(xù)的 1GB 大小的內(nèi)存空間，那照樣無法申請一個 1GB 大小的數(shù)組谦趣。而我們的二分查找是作用在數(shù)組這種數(shù)據(jù)結(jié)構(gòu)之上的疲吸，所以太大的數(shù)據(jù)用數(shù)組存儲就比較吃力了，也就不能用二分查找了前鹅。
解答開篇
二分查找的理論知識你應(yīng)該已經(jīng)掌握了摘悴。我們來看下開篇的思考題：如何在 1000 萬個整數(shù)中快速查找某個整數(shù)？
這個問題并不難舰绘。我們的內(nèi)存限制是 100MB蹂喻，每個數(shù)據(jù)大小是 8 字節(jié)葱椭，最簡單的辦法就是將數(shù)據(jù)存儲在數(shù)組中，內(nèi)存占用差不多是 80MB口四，符合內(nèi)存的限制孵运。借助今天講的內(nèi)容，我們可以先對這 1000 萬數(shù)據(jù)從小到大排序蔓彩，然后再利用二分查找算法掐松，就可以快速地查找想要的數(shù)據(jù)了。
看起來這個問題并不難粪小，很輕松就能解決大磺。實(shí)際上，它暗藏了“玄機(jī)”探膊。如果你對數(shù)據(jù)結(jié)構(gòu)和算法有一定了解杠愧，知道散列表、二叉樹這些支持快速查找的動態(tài)數(shù)據(jù)結(jié)構(gòu)逞壁。你可能會覺得流济，用散列表和二叉樹也可以解決這個問題。實(shí)際上是不行的腌闯。
雖然大部分情況下绳瘟，用二分查找可以解決的問題，用散列表姿骏、二叉樹都可以解決糖声。但是，我們后面會講分瘦，不管是散列表還是二叉樹蘸泻，都會需要比較多的額外的內(nèi)存空間。如果用散列表或者二叉樹來存儲這 1000 萬的數(shù)據(jù)嘲玫，用 100MB 的內(nèi)存肯定是存不下的悦施。而二分查找底層依賴的是數(shù)組，除了數(shù)據(jù)本身之外去团，不需要額外存儲其他信息抡诞，是最省內(nèi)存空間的存儲方式，所以剛好能在限定的內(nèi)存大小下解決這個問題土陪。
內(nèi)容小結(jié)
今天我們學(xué)習(xí)了一種針對有序數(shù)據(jù)的高效查找算法昼汗，二分查找，它的時間復(fù)雜度是 O(logn)旺坠。
二分查找的核心思想理解起來非常簡單乔遮，有點(diǎn)類似分治思想扮超。即每次都通過跟區(qū)間中的中間元素對比取刃，將待查找的區(qū)間縮小為一半蹋肮，直到找到要查找的元素，或者區(qū)間被縮小為 0璧疗。但是二分查找的代碼實(shí)現(xiàn)比較容易寫錯坯辩。你需要著重掌握它的三個容易出錯的地方：循環(huán)退出條件、mid 的取值崩侠，low 和 high 的更新漆魔。
二分查找雖然性能比較優(yōu)秀，但應(yīng)用場景也比較有限却音。底層必須依賴數(shù)組改抡，并且還要求數(shù)據(jù)是有序的。對于較小規(guī)模的數(shù)據(jù)查找系瓢，我們直接使用順序遍歷就可以了阿纤，二分查找的優(yōu)勢并不明顯。二分查找更適合處理靜態(tài)數(shù)據(jù)夷陋，也就是沒有頻繁的數(shù)據(jù)插入欠拾、刪除操作。
課后思考
如何編程實(shí)現(xiàn)“求一個數(shù)的平方根”骗绕？要求精確到小數(shù)點(diǎn)后 6 位藐窄。
我剛才說了，如果數(shù)據(jù)使用鏈表存儲酬土，二分查找的時間復(fù)雜就會變得很高荆忍，那查找的時間復(fù)雜度究竟是多少呢？如果你自己推導(dǎo)一下撤缴，你就會深刻地認(rèn)識到东揣，為何我們會選擇用數(shù)組而不是鏈表來實(shí)現(xiàn)二分查找了。
經(jīng)典回復(fù)
二分法求一個數(shù)x的平方根y腹泌？
解答：根據(jù)x的值嘶卧，判斷求解值y的取值范圍。假設(shè)求解值范圍min < y < max凉袱。若0<x<1芥吟，則min=x，max=1专甩；若x=1钟鸵，則y=1；x>1涤躲，則min=1棺耍，max=x；在確定了求解范圍之后种樱，利用二分法在求解值的范圍中取一個中間值middle=(min+max)÷2蒙袍，判斷middle是否是x的平方根俊卤？若(middle+0.000001)(middle+0.000001)＞x且(middle-0.000001)(middle-0.000001)<x，根據(jù)介值定理害幅，可知middle既是求解值;若middlemiddle > x消恍，表示middle＞實(shí)際求解值，max=middle; 若middlemiddle ＜ x以现，表示middle＜實(shí)際求解值狠怨，min =middle;之后遞歸求解！
備注：因?yàn)槭潜Ａ?位小數(shù)邑遏，所以middle上下浮動0.000001用于介值定理的判斷
說說第二題吧佣赖，感覺爭議比較大:
假設(shè)鏈表長度為n，二分查找每次都要找到中間點(diǎn)(計(jì)算中忽略奇偶數(shù)差異):
第一次查找中間點(diǎn)记盒，需要移動指針n/2次茵汰；
第二次，需要移動指針n/4次孽鸡；
第三次需要移動指針n/8次蹂午；
......
以此類推，一直到1次為值
總共指針移動次數(shù)(查找次數(shù)) = n/2 + n/4 + n/8 + ...+ 1彬碱，這顯然是個等比數(shù)列豆胸，根據(jù)等比數(shù)列求和公式：Sum = n - 1.
最后算法時間復(fù)雜度是：O(n-1)，忽略常數(shù)巷疼，記為O(n)晚胡，時間復(fù)雜度和順序查找時間復(fù)雜度相同
但是稍微思考下，在二分查找的時候嚼沿，由于要進(jìn)行多余的運(yùn)算估盘，嚴(yán)格來說，會比順序查找時間慢
個人覺得二分查找進(jìn)行優(yōu)化時骡尽，還個細(xì)節(jié)注意：
將mid = lo + (hi - lo) /2遣妥，將除法優(yōu)化成移位運(yùn)算時，得注意運(yùn)算符的優(yōu)先級攀细，千萬不能寫成這樣：mid = lo + (hi - lo) >> 1
