DIV CSS 佈局教程網

資料檢索演算法:順序搜尋、極值查找與二分搜尋
編輯:關於JavaScript     

查找資料基本上有兩條路:順序搜尋與二分搜尋。順序搜尋適用於任意排列的資料,實作單純;二分搜尋效率高得多,但前提是資料必須已排序。本文把這兩者與相關的極值查找、重複值計數一起整理。

一、順序搜尋(Sequential Search)

從第一個元素開始逐個比對,直到找到或走完整個清單。

// 回傳布林值
function seqSearch(data, arr) {
  for (var i = 0; i < arr.length; ++i) {
    if (arr[i] == data) {
      return true;
    }
  }
  return false;
}

// 回傳位置,找不到則回 -1(實務上更有用)
function seqSearch(data, arr) {
  for (var i = 0; i < arr.length; ++i) {
    if (arr[i] == data) {
      return i;
    }
  }
  return -1;
}

時間複雜度 O(n),平均需比較 n/2 次。

二、查找最小值與最大值

演算法步驟(以最小值為例):

1. 把第一個元素設為目前最小值。

2. 從第二個元素開始依序與目前最小值比較。

3. 若當前元素更小,就把它設為新的最小值。

4. 前進到下一個元素,重複步驟 3。

5. 走訪結束時,變數中存的就是最小值。

function findMin(arr) {
  var min = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

function findMax(arr) {
  var max = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

兩者都是 O(n)。實務上 Math.min(...arr) 更簡潔,但資料量龐大時有參數上限問題,此時用 reduce 一次同時取極值會更好。

三、二分搜尋(Binary Search)

演算法步驟:

1. 下邊界定為 0,上邊界定為 length − 1。

2. 當下邊界 <= 上邊界時:

  A. 中點 = (上邊界 + 下邊界) / 2 取整數。

  B. 中點值 < 目標 → 下邊界 = 中點 + 1。

  C. 中點值 > 目標 → 上邊界 = 中點 − 1。

  D. 相等 → 找到,回傳位置。

3. 迴圈結束仍未回傳,代表不存在,回傳 -1。

function binSearch(data, arr) {
  var lowerBound = 0;
  var upperBound = arr.length - 1;

  while (lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound) / 2);
    if (arr[mid] < data) {
      lowerBound = mid + 1;
    } else if (arr[mid] > data) {
      upperBound = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

時間複雜度 O(log n),這是它與順序搜尋最關鍵的差異。

四、搭配排序使用

二分搜尋要求輸入有序,所以實用上通常先排序。以下用快速排序把整組流程串起來:

function qSort(list) {
  if (list.length == 0) return [];

  var left = [];    // 小於基準值
  var right = [];   // 大於或等於基準值
  var pivot = list[0];

  for (var i = 1; i < list.length; i++) {
    if (list[i] < pivot) {
      left.push(list[i]);
    } else {
      right.push(list[i]);
    }
  }
  return qSort(left).concat(pivot, qSort(right));
}

var numbers = [0, 9, 1, 8, 7, 6, 2, 3, 5, 4];
var list = qSort(numbers);
console.log(binSearch(6, list));   // 5

五、計算重複出現的次數

binSearch 找到目標時,只保證停在「某一個」符合的位置,其他相同值可能落在它左側或右側。最直覺的做法是從該位置向兩邊各走一趟,連續相同就計數:

function count(data, arr) {
  var count = 0;
  var positions = [];
  var position = binSearch(data, arr);

  if (position > -1) {
    ++count;
    positions.push(position);

    // 向左掃
    for (var i = position - 1; i >= 0; --i) {
      if (arr[i] == data) {
        ++count;
        positions.push(i);
      } else {
        break;
      }
    }

    // 向右掃
    for (var j = position + 1; j < arr.length; ++j) {
      if (arr[j] == data) {
        ++count;
        positions.push(j);
      } else {
        break;
      }
    }
  }
  return { count: count, positions: positions };
}

var arr = [0, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(count(1, arr));

執行結果如下圖:

補充:兩個實務提醒

重複值多的情況可用「找邊界」。上面向兩側掃描在「全部元素都相同」時會退化為 O(n)。更穩健的做法是寫 lowerBound 與 upperBound 兩個變體二分搜尋,各自找出區間起訖,重複次數就是兩者相減,整體維持 O(log n)。

注意 == 與 === 的差別。本文範例沿用 == 以便說明演算法;實務上請用 ===,避免 "1" 與 1 這類型別混淆造成誤判。

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