DIV CSS 佈局教程網

二元搜尋(折半查找)原理與 JavaScript 實作
編輯:關於JavaScript     

演算法思路

折半查找只適用於有序表。每次把待查值與當前範圍的中間元素比較,會有三種結果:

  1. 相等 — 直接回傳中間位置的索引。
  2. 待查值較小 — 取範圍的前半段作為新範圍,重複步驟一。
  3. 待查值較大 — 取範圍的後半段作為新範圍,重複步驟一。

若範圍收斂至空仍未找到,回傳 -1 表示失敗。

用二元樹來理解會更直觀:中間值就是根節點,前半段是左子樹,後半段是右子樹。因此單次查找所需的比較次數,正好等於該元素所在的層數;在等機率分佈下約為 log2(n+1) - 1,遠優於線性搜尋的 n 次。

C 語言版本

迴圈寫法:

int BiSearch(int data[], const int x, int beg, int last)
{
  int mid;
  if (beg > last) return -1;
  while (beg <= last)
  {
    mid = (beg + last) / 2;
    if (x == data[mid])      return mid;
    else if (data[mid] < x)  beg  = mid + 1;
    else if (data[mid] > x)  last = mid - 1;
  }
  return -1;
}

遞迴寫法:

int IterBiSearch(int data[], const int x, int beg, int last)
{
  int mid = (beg + last) / 2;
  if (x == data[mid])          return mid;
  else if (x < data[mid])      return IterBiSearch(data, x, beg, mid - 1);
  else if (x > data[mid])      return IterBiSearch(data, x, mid + 1, last);
  return -1;
}

JavaScript 版本

/**
 * 在有序列表中折半查找,回傳索引;找不到回傳 -1
 * @param {Array} array 被搜尋的陣列
 * @param {*}     x     要尋找的值
 */
function binarySearch(array, x) {
  var lowPoint = 1,
      higPoint = array.length,
      returnValue = -1,
      midPoint,
      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'));

這裡有個實作細節值得注意:程式中把索引設計成從 1 起算,存取時才減 1,好讓「找不到」時能用 0 之外的 -1 明確表達失敗,避免與合法索引混淆。

幾個實務提醒

  • 原始碼中常見的 else if (x = array[mid]) 是 assignment 而非比較,永遠為真值,屬於典型的 debug 陷阱,撰寫時應使用 ===。
  • (beg + last) / 2 在大型陣列上可能整數溢位,Java 等語言建議寫成 beg + (last - beg) / 2;JavaScript 因使用雙精度浮點,短期間不是問題。
  • 若表中有重複元素,標準折半查找回傳的是「任一」符合位置,而非第一個或最後一個。需要邊界時得改寫成尋找下界/上界的變體。
  • 資料量小或需頻繁插入刪除時,線性搜尋反而更划算,因為它沒有「資料必須先排序」這個前置成本。
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved