← 返回完整题库
JavaScript中等

实现 js 二分查找

参考答案

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = (left + right) >> 1;         // 或 left + ((right-left)>>1) 防溢出
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

要点:

  • 前提是有序数组;
  • 边界用 <=,退出时 left > right;
  • >>1 可避免浮点,但大数需注意 32 位限制;推荐 Math.floor((l + r) / 2);
  • 找左右边界(第一个 ≥ target /最后一个 ≤)用变体:命中后继续收缩;
  • 复杂度 O(log n)。

本题来自 计算机知识面试题库,共 921 道题。