對分查找

對分查找是一種效率很高的查找方法，但被查找的數據必須是有序（例如非遞減有序）的。

基本介紹

• 中文名：對分查找
• 前提：待查找的數據必須是有序的
• 原理：被查找的數據必須是有序
• 優勢：效率要遠高於順序查找

前提

對分查找的前提是待查找的數據必須是有序的。

原理

對分查找首先將查找鍵與有序數組內處於中間位置的元素進行比較，如果中間位置上的元素內的數值與查找鍵不同，根據數組元素的有序性，就可確定應該在數組的前半部分還是後半部分繼續進行查找；在新確定的範圍內，繼續按上述方法進行查找，直到獲得最終結果。

在數組中的數據是有序的，如果是增序的，是指下標越小的數組元素中存儲的數據也越小，減序則相反。設數組變數d中存儲了n個互不相同的數據，則數組變數d中的數據是增序時，有：

d(1)<d(2)<…d(i)<d(i+1)<…<d(n-1)<d(n)

優勢

由於對分查找每查找一次，查找範圍就縮小一半，因此效率要遠高於順序查找。

流程圖

對分查找的程式流程圖（略圖）