DIV CSS 佈局教程網

用 JavaScript 實作二分搜尋:在有序陣列中快速定位元素
編輯:關於JavaScript     

在一個「已經排好序」的陣列裡找目標,逐個比對顯得有點笨。二分搜尋(折半查找)的思路是:每次都拿中間那個元素跟目標比,比目標小就往右半邊找,比目標大就往左半邊找,每次都能砍掉一半的資料。n 個元素最多只需 log₂n 次比較——一千筆資料約十次就夠了。

實作

/**
 * 折半查找字符在数组中的位置(有序列表)
 * @param array 被检索的数组
 * @param x     要查找的字符
 * @returns     字符在数组中的位置,没找到返回 -1
 */
function binarySearch(array, x){
    var lowPoint  = 1;
    var higPoint  = array.length;
    var returnValue = -1;
    var midPoint;
    var 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'));

幾個容易踩的細節

  • 下標要減一:程式裡的 lowPoint / higPoint 用的是「第幾個」的思維(從 1 開始數),而陣列下標從 0 開始,所以取用時一律寫成 array[midPoint - 1]。這是最常出錯的地方。
  • 取中間用 Math.ceil:偶數長度時中間會落在小數點,用 ceil 往上取整可以確保 lowPoint 一定會前進,避免無窮迴圈。
  • 迴圈條件是 low <= high:寫成 < 會漏掉只剩一個元素的情況。
  • 找不到回傳 -1:讓呼叫端能用 if (pos >= 0) 直接判斷,不必另外準備例外處理。

一個小提醒

原範例中最後的相等判斷寫成了 else if (x = array[midPoint - 1])——那是指派而非比較,會永遠為真。實務上請寫成 ===,並把常數放在左側(=== 加上左值寫法),可以讓這類筆誤在執行前就被發現。

另外要牢記前提:二分搜尋只能用在已排序的資料上。如果來源是未排序的陣列,先 sort() 再搜,或者改用 indexOf 之類的線性搜尋,取決於你查詢的頻率。

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