萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 二分查找算法實現:有序數組高效查找、遞歸與迭代雙版本

算法原理

前提:**數組必須有序(升序)**。
每次取中間索引 mid = Math.floor((low+high)/2),比較 arr[mid] 與目標值:

  • 相等 → 返回 mid
  • 目標值較小 → 高半區 high = mid - 1
  • 目標值較大 → 低半區 low = mid + 1

時間複雜度 O(log n),空間 O(1)(迭代)或 O(log n)(遞歸棧)。

遞歸版本

function binarySearchRecursive(arr, target, low, high) {
  if (low > high) return -1;
  var mid = Math.floor((low + high) / 2);
  if (arr[mid] === target) return mid;
  return arr[mid] > target
    ? binarySearchRecursive(arr, target, low, mid - 1)
    : binarySearchRecursive(arr, target, mid + 1, high);
}

// 調用
var arr = [3,5,6,7,9,12,15];
console.log(binarySearchRecursive(arr, 15, 0, arr.length-1)); // 6

迭代版本(推薦生產)

function binarySearchIterative(arr, target) {
  var low = 0, high = arr.length - 1;
  while (low <= high) {
    var mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] > target) high = mid - 1;
    else low = mid + 1;
  }
  return -1;
}

進階變體

1. 查找第一個/最後一個等於目標值的索引(含重複元素)

function lowerBound(arr, target) { // 第一個 >= target
  var low = 0, high = arr.length;
  while (low < high) {
    var mid = (low + high) >> 1;
    if (arr[mid] < target) low = mid + 1;
    else high = mid;
  }
  return low;
}
function upperBound(arr, target) { // 第一個 > target
  var low = 0, high = arr.length;
  while (low < high) {
    var mid = (low + high) >> 1;
    if (arr[mid] <= target) low = mid + 1;
    else high = mid;
  }
  return low;
}
// 目標值出現範圍 [lowerBound, upperBound-1]

2. 旋轉有序數組查找

function searchRotated(arr, target) {
  var low = 0, high = arr.length - 1;
  while (low <= high) {
    var mid = (low + high) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[low] <= arr[mid]) { // 左半有序
      if (arr[low] <= target && target < arr[mid]) high = mid - 1;
      else low = mid + 1;
    } else { // 右半有序
      if (arr[mid] < target && target <= arr[high]) low = mid + 1;
      else high = mid - 1;
    }
  }
  return -1;
}

JS 特有優化技巧

  • >> 0 或 | 0 快速取整(位運算比 Math.floor 快)
  • 避免 (low+high)/2 溢出(JS 數字安全整數 2⁵³-1,實際極少溢出,但習慣用 low + ((high-low)>>1))
  • 對象數組查找時提取比較鍵值,或傳入 compareFn

何時不用二分?

  • 數組未排序 → 先排序 O(n log n) 再查不如線性 O(n)
  • 數據量極小(<50)線性查找更快(分支預測、緩存局部性)
  • 頻繁插入/刪除 → 平衡樹/跳表/Map 更適合
copyright © 萬盛學電腦網 all rights reserved