二分搜尋(又稱折半搜尋)是第一個每個 programmer 都該學會的演算法。它的比較次數少、速度快、平均表現優異;代價是資料必須先排序,而且插入刪除的成本高。因此它最適合「偶爾變動、頻繁查詢」的有序資料。
假設陣列已按升冪排列。先拿中間位置的元素與目標比較:
重複以上步驟,直到找到目標,或子區間不存在為止(此時搜尋失敗)。每一次比較都能砍掉一半的候選範圍,這就是它為何是 O(log n)。
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
if (low <= high) {
if (arr[low] == find) return low;
if (arr[high] == find) return high;
var mid = Math.ceil((high + low) / 2);
if (arr[mid] == find) {
return mid;
} else if (arr[mid] > find) {
return binary(find, arr, low, mid - 1);
} else {
return binary(find, arr, mid + 1, high);
}
}
return -1;
}
binary(15, Arr, 0, Arr.length - 1);
開頭先比對 low 與 high 兩個端點,是一個實用的小優化:能提前命中邊界元素,少走幾輪遞迴。遞迴的終止條件是 low <= high 不再成立,此時回傳 -1 代表找不到。
遞迴好讀,但每一層都要佔用堆疊空間。等價的迴圈寫法如下:
function binary(find, arr) {
var low = 0, high = arr.length - 1;
while (low <= high) {
var mid = Math.floor((low + high) / 2);
if (arr[mid] === find) return mid;
if (arr[mid] > find) { high = mid - 1; }
else { low = mid + 1; }
}
return -1;
}
補充兩點實務知識:計算 mid 時若 low 與 high 都可能非常大,(low + high) 有溢位風險,改用 low + Math.floor((high - low) / 2) 更安全;另外 JS 引擎的 Array.prototype.indexOf、以及 sort 之後的搜尋,多數情境已經夠快,二分搜尋真正的舞台是資料量大到必須自己處理的情況。