陳新龍

二分查找（折半查找）是一種效率較高的查找方法，但是二分查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

假設(shè)有1-100的數(shù)字，隨機(jī)選擇其中一個(gè)數(shù)字（假設(shè)為63），每次猜測(cè)后會(huì)對(duì)結(jié)果判斷，提示大還是小。什么方法能保證以最少的次數(shù)猜到數(shù)字呢？

假設(shè)從1開(kāi)始猜，依次遞增1的辦法要猜63次。這就是順序查找算法了，目標(biāo)數(shù)字越大效率越低。

如果使用二分查找，第一次便從50開(kāi)始猜（100的一半），雖然猜的數(shù)字小于目標(biāo)數(shù)字，但是我們已經(jīng)排除了接近一半的數(shù)字；第二次猜75（50-100的一半），雖然猜的數(shù)字大于結(jié)果，但是我們又排除了剩下數(shù)字的一半（75-100）；第三次我們猜63（50-75 的一半）剛剛好是正確答案。

通過(guò)對(duì)比我們可以發(fā)現(xiàn)二分查找很明顯要比順序查找效率高很多。相信你已經(jīng)看懂二分查找的道理了，接下來(lái)小陳老師通過(guò)代碼給大家梳理一下二分查找的內(nèi)容。

首先創(chuàng)建一個(gè)有序列表用于存放待查詢的數(shù)組內(nèi)容（11，22，33，44，55，66），通過(guò)詢問(wèn)用戶想查找的數(shù)值（假設(shè)用戶想查找數(shù)字55），若數(shù)值存在則輸出結(jié)果和數(shù)值的位置；若數(shù)值不存在，提示數(shù)值不存在此列表中。

在實(shí)現(xiàn)二分查找的過(guò)程中我們通過(guò)設(shè)置變量left 和right 控制一個(gè)循環(huán)來(lái)查找元素（left 和right 相當(dāng)于我們查找序列的的左邊界值和右邊界值）。列表中存在六個(gè)數(shù)，left 和right 分別為1 和6（后續(xù)結(jié)果中若計(jì)算出小數(shù)就向下取整），在循環(huán)每次迭代的過(guò)程中，將middle 設(shè)置為left和right 的中間值， 如left=1，right=6的時(shí)候，middle 等同于（1+6）/2=3， 也就是3，對(duì)應(yīng)的值為33，很顯然33小于55，那么我們便可以排除前三項(xiàng)內(nèi)容。

將索引值移動(dòng)到middle 后一個(gè)元素的位置上，也就是left = middle+1，right 不變，代表著下一組搜索到的區(qū)域便是當(dāng)前數(shù)據(jù)集的右半?yún)^(qū)。如果middle的元素值比目標(biāo)元素大，那么右索引移動(dòng)到middle 前一個(gè)元素的位置上。也就是right = middle-1，left 不變，代表下一組搜索的區(qū)域便是當(dāng)前數(shù)據(jù)集的左半?yún)^(qū)。

我們可以發(fā)現(xiàn)一個(gè)規(guī)律，left 從左向右移動(dòng)，right 從右向左移動(dòng)， 一旦middle 所對(duì)應(yīng)的元素是我們需要查找的數(shù)字，代表找到目標(biāo)，查找結(jié)束。如果在執(zhí)行的過(guò)程中列表中沒(méi)有所查找的數(shù)字，那么最后結(jié)束的標(biāo)志則是right 小于left。

二分查找算是一種高效的算法，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好，但是也有一定的缺點(diǎn)，要求待查表為有序表，且插入困難，因此二分查找適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。