二分搜尋(binary search,又稱折半搜尋)的優點很明確:比較次數少、速度快、平均表現好。缺點同樣明確:它要求資料必須先排好序,而且在中間插入或刪除元素成本很高。因此它最適合「偶爾變動、頻繁查詢」的有序集合。
假設資料已按升序排列:
1. 把中間位置的元素拿出來和目標值比較,相等就找到了。
2. 若中間值大於目標,目標只可能在「前半段」。
3. 若中間值小於目標,目標只可能在「後半段」。
4. 重複上述過程,直到找到,或子區間不存在(low > high)代表搜尋失敗。
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); // 6
取中點不要寫 (low + high) / 2。當陣列很長時兩數相加可能超出整數上限而算出負數,安全寫法是 low + (high - low) / 2,在 JavaScript 中還要注意要搭配 Math.floor 取整數。
確認資料真的有序。二分搜尋不會幫你檢查排序,若傳入未排序的陣列,它會安靜地回傳錯誤答案——這是最難 debug 的一類 bug。若資料來源不確定,先在函式開頭做一次 O(n) 的排序檢查,或在呼叫端就固定用同一份已排序的資料。