DIV CSS 佈局教程網

二分搜尋法:為什麼它快,又為什麼有前提條件
編輯:關於JavaScript     

二分搜尋(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) 的排序檢查,或在呼叫端就固定用同一份已排序的資料。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved