DIV CSS 佈局教程網

JavaScript 二分搜尋演算法:在有序陣列裡快速查找
編輯:關於JavaScript     

二分搜尋(又稱折半搜尋)是第一個每個 programmer 都該學會的演算法。它的比較次數少、速度快、平均表現優異;代價是資料必須先排序,而且插入刪除的成本高。因此它最適合「偶爾變動、頻繁查詢」的有序資料。

演算法邏輯

假設陣列已按升冪排列。先拿中間位置的元素與目標比較:

  1. 兩者相等 → 搜尋成功,回傳索引。
  2. 中間值大於目標 → 目標只可能在「前半段」,繼續在前半段搜尋。
  3. 中間值小於目標 → 目標只可能在「後半段」,繼續在後半段搜尋。

重複以上步驟,直到找到目標,或子區間不存在為止(此時搜尋失敗)。每一次比較都能砍掉一半的候選範圍,這就是它為何是 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 之後的搜尋,多數情境已經夠快,二分搜尋真正的舞台是資料量大到必須自己處理的情況。

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