Scratch二分查找算法練習

陳新龍

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

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

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

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

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

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

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

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

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

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