Scratch二分查找算法練習

陳新龍

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

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

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

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

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

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

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

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

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

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