折半查找只適用於有序表。每次把待查值與當前範圍的中間元素比較,會有三種結果:
若範圍收斂至空仍未找到,回傳 -1 表示失敗。
用二元樹來理解會更直觀:中間值就是根節點,前半段是左子樹,後半段是右子樹。因此單次查找所需的比較次數,正好等於該元素所在的層數;在等機率分佈下約為 log2(n+1) - 1,遠優於線性搜尋的 n 次。
迴圈寫法:
int BiSearch(int data[], const int x, int beg, int last)
{
int mid;
if (beg > last) return -1;
while (beg <= last)
{
mid = (beg + last) / 2;
if (x == data[mid]) return mid;
else if (data[mid] < x) beg = mid + 1;
else if (data[mid] > x) last = mid - 1;
}
return -1;
}
遞迴寫法:
int IterBiSearch(int data[], const int x, int beg, int last)
{
int mid = (beg + last) / 2;
if (x == data[mid]) return mid;
else if (x < data[mid]) return IterBiSearch(data, x, beg, mid - 1);
else if (x > data[mid]) return IterBiSearch(data, x, mid + 1, last);
return -1;
}
/**
* 在有序列表中折半查找,回傳索引;找不到回傳 -1
* @param {Array} array 被搜尋的陣列
* @param {*} x 要尋找的值
*/
function binarySearch(array, x) {
var lowPoint = 1,
higPoint = array.length,
returnValue = -1,
midPoint,
found = false;
while (lowPoint <= higPoint && !found) {
midPoint = Math.ceil((lowPoint + higPoint) / 2);
if (x > array[midPoint - 1]) {
lowPoint = midPoint + 1;
} else if (x < array[midPoint - 1]) {
higPoint = midPoint - 1;
} else {
found = true;
}
}
if (found) returnValue = midPoint;
return returnValue;
}
var array2 = ['a','b','c','d','e','f','g'];
console.log(binarySearch(array2, 'c'));
這裡有個實作細節值得注意:程式中把索引設計成從 1 起算,存取時才減 1,好讓「找不到」時能用 0 之外的 -1 明確表達失敗,避免與合法索引混淆。
else if (x = array[mid]) 是 assignment 而非比較,永遠為真值,屬於典型的 debug 陷阱,撰寫時應使用 ===。(beg + last) / 2 在大型陣列上可能整數溢位,Java 等語言建議寫成 beg + (last - beg) / 2;JavaScript 因使用雙精度浮點,短期間不是問題。