Chrome 浏览器插件

Appearance

前端 JS/TS 算法：二分查找（Binary Search）指南 ​

本文档旨在为前端开发者提供一份关于二分查找算法的完整、实用的指南，从应用场景、核心原理到工程实践，全面覆盖该算法在 JS/TS 中的应用。

一、 引言 / 场景动机 ​

在前端领域，我们通常处理的数据量不大，简单的线性查找 (Array.prototype.find) 似乎够用。然而，在追求极致性能和流畅体验的场景下，二分查找是不可或缺的利器。它的 O(log n) 复杂度能将百万级数据的查找次数降低到 20 次以内，带来质的飞跃。

前端核心应用场景：

  • 虚拟滚动 / 无限列表：当用户滚动到指定位置时，需要快速计算出视口中应该渲染哪几项数据。在拥有成千上万条数据的列表中，二分查找能根据滚动偏移量，瞬间定位到对应的项目索引。
  • 搜索自动补全：对已排序的搜索建议列表，二分查找可以极快地找到用户输入前缀的起始与结束位置，从而高效筛选出匹配项。
  • 性能监控 / 时间轴：在复杂的性能时间轴或视频弹幕中，需要根据给定的时间戳（如 1m30.5s）精确插入或定位一个事件。二分查找是实现此功能的不二之选。
  • 源码映射 (Source Map)：在调试时，需要根据编译后代码的行列号，快速在 .map 文件中找到对应的源码位置，这个过程也应用了二分查找的变体。

二、 前置条件 ​

二分查找并非万能，它的高效源于两个严格的前置条件：

  1. 有序性 (Sorted)：目标数据集必须是已排序的。可以是升序、降序，或根据自定义比较函数（comparator）排序。对于无序数据使用二分查找会得到错误结果。
  2. 可随机访问 (Random Access)：必须能够通过索引在 O(1) 时间内访问到任何元素。这意味着 Array、TypedArray、字符串等是理想载体，而 Map、Set 或 链表 则不适用（即使它们的元素逻辑上有序）。

三、 算法原理 ​

二分查找的核心思想是"分而治之"。它不断将搜索空间一分为二，通过比较中间值与目标值，来排除掉一半不可能包含目标的区间。

1. 线性检索 vs. 二分查找示意图 ​

text
// 线性查找: O(n)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  target = 9
 ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑
(逐个检查，最坏情况 n 次)

// 二分查找: O(log n)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  target = 9
 L             M              H  (mid=5, 5<9, L=M+1)
               L  M        H     (mid=8, 8<9, L=M+1)
                        L,M,H     (mid=9, 9=9, found!)
(最多 4 次)

2. 循环不变式 (Loop Invariant) ​

这是理解并写对二分查找的关键。在整个循环过程中，我们始终要维护一个性质：如果目标值 target 存在于数组中，那它一定在闭区间 [low, high] 之内。循环的每一步都旨在缩小这个区间，同时保持该性质不变。

3. Mid 计算方式 ​

为避免在处理超大数组时（在 JS 中不常见，但在其他语言如 Java 中可能）因 low + high 溢出整数范围，推荐使用以下方式计算中间索引：

javascript
const mid = low + Math.floor((high - low) / 2);
// 或使用位运算，效率更高
const mid = low + ((high - low) >> 1);

四、 复杂度分析 ​

1. 时间复杂度: O(log n) ​

每次迭代都将搜索空间减半。对于大小为 n 的数组，最多需要 log₂(n) 次比较。这是其性能优势的核心。

2. 空间复杂度: O(1) (迭代版) / O(log n) (递归版) ​

迭代版：仅使用有限的几个变量 (low, high, mid)，空间是固定的。 递归版：每次递归调用都会产生一个新的函数调用栈帧，栈的深度最多为 log n。

五、 基准实现 ​

1. Iterative ES2023 版 (推荐) ​

javascript
/**
 * 标准的迭代式二分查找
 * @param {number[]} sortedArray - 已升序排列的数组
 * @param {number} target - 目标值
 * @returns {number} - 找到则返回索引，否则返回 -1
 */
function binarySearch(sortedArray, target) {
  let low = 0;
  let high = sortedArray.length - 1;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    const midValue = sortedArray[mid];

    if (midValue === target) {
      return mid;
    } else if (midValue < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // 未找到
}

2. Recursive TS 版 (带泛型与比较器) ​

typescript
type Comparator<T> = (a: T, b: T) => number;

/**
 * 递归式二分查找，支持泛型和自定义比较器
 * @param arr - 只读的已排序数组
 * @param target - 目标值
 * @param comparator - 比较函数 (返回 <0, 0, >0)
 * @returns 找到则返回索引，否则返回 -1
 */
function binarySearchRecursive<T>(
  arr: readonly T[],
  target: T,
  comparator: Comparator<T>
): number {
  const search = (low: number, high: number): number => {
    if (low > high) {
      return -1;
    }
    const mid = low + ((high - low) >> 1);
    const comparison = comparator(arr[mid], target);

    if (comparison === 0) {
      return mid;
    } else if (comparison < 0) {
      return search(mid + 1, high);
    } else {
      return search(low, mid - 1);
    }
  };
  return search(0, arr.length - 1);
}

3. 单元测试用例 (Jest / Vitest) ​

javascript
// vitest
import { describe, it, expect } from 'vitest';
import { binarySearch } from './binarySearch';

describe('binarySearch', () => {
  const arr = [1, 3, 5, 7, 9, 11, 13];
  it('should find an existing element', () => {
    expect(binarySearch(arr, 9)).toBe(4);
  });
  it('should return -1 for a non-existing element', () => {
    expect(binarySearch(arr, 4)).toBe(-1);
  });
  it('should handle edge cases: first and last elements', () => {
    expect(binarySearch(arr, 1)).toBe(0);
    expect(binarySearch(arr, 13)).toBe(6);
  });
  it('should handle empty array', () => {
    expect(binarySearch([], 5)).toBe(-1);
  });
});

六、 常见变体 ​

实际业务中，标准二分查找往往不够，以下变体覆盖了 80% 的场景。

1. 查找第一个等于 target 的元素 ​

当找到 target 时，不要立即返回，而是记录当前索引，并尝试在左半部分继续寻找 (high = mid - 1)。

typescript
const findFirst = <T>(arr: readonly T[], target: T, comparator: Comparator<T>): number => {
  let low = 0;
  let high = arr.length - 1;
  let result = -1;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    const comparison = comparator(arr[mid], target);

    if (comparison >= 0) {
      if (comparison === 0) {
        result = mid; // 找到一个潜在答案
      }
      high = mid - 1; // 继续向左寻找第一个
    } else {
      low = mid + 1;
    }
  }
  return result;
};

2. 查找最后一个等于 target 的元素 ​

与上一个类似，当找到 target 时，记录索引，并尝试在右半部分继续寻找 (low = mid + 1)。

3. Lower Bound: 查找第一个大于或等于 target 的元素。 ​

这是 git bisect 或定位插入点的核心。

4. Upper Bound: 查找第一个大于 target 的元素。 ​

5. 查找旋转数组中的最小值 ​

例如 [4, 5, 6, 7, 0, 1, 2]。通过比较 mid 与 high 的值来判断哪部分是有序的，从而收缩区间。

6. 按条件二分（函数单调性） ​

不直接操作数组，而是对一个满足单调性的函数 f(x) 求解，如找到满足 f(x) === true 的最小 x。这在"答案值域"上进行二分，非常强大。

七、 TypeScript 泛型封装 ​

为了打造一个健壮、可复用的工具函数，我们可以设计一个更完善的 TS 泛型版本，并约定返回值。

typescript
/**
 * 在有序数组中查找 target 的索引。
 * 如果找不到，返回一个负数 `-(insertionPoint + 1)`，
 * `insertionPoint` 是为保持数组有序，target 应该插入的位置。
 *
 * @param arr 只读的有序数组
 * @param target 目标值
 * @param cmp 比较器，默认为数字升序比较
 * @returns 找到则返回索引，否则返回 `-(insertionPoint + 1)`
 */
const binarySearchAdvanced = <T>(
  arr: readonly T[],
  target: T,
  cmp: (a: T, b: T) => number = (a: any, b: any) => a - b
): number => {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    const comparison = cmp(arr[mid], target);

    if (comparison < 0) {
      low = mid + 1;
    } else if (comparison > 0) {
      high = mid - 1;
    } else {
      return mid; // 找到
    }
  }

  return -(low + 1); // 未找到，返回插入点
};

使用示例：

typescript
const arr = [2, 5, 8, 12];
const index = binarySearchAdvanced(arr, 7); // returns -3
if (index < 0) {
  const insertionPoint = -(index + 1); // 2
  console.log(`7 should be inserted at index ${insertionPoint}`);
}

八、 易错边界 & 调试技巧 ​

二分查找的 bug 99% 都出在边界条件上。

1. low < high vs low <= high ​

使用 low <= high 通常更直观，它意味着搜索区间 [low, high] 是闭合的。此时，如果 arr[mid] 不等于 target，low 和 high 的更新应该是 mid + 1 和 mid - 1，以确保 mid 本身被排除。 使用 low < high 时，循环在 low === high 时终止，需要在循环外单独处理这个点。

2. 无限循环根因 ​

当 high 的更新写成 high = mid 时，如果 low 和 high 相邻（high = low + 1），mid 会等于 low，若此时需要收缩右边界，high 将保持不变，导致无限循环。

3. 浮点数 mid ​

mid 必须是整数索引，Math.floor() 或位运算是必要的。

4. 调试技巧 ​

console.table({ low, high, mid, midValue: arr[mid] }): 在循环体内加入此行，可以清晰地看到每一步区间的收缩情况。 performance.now(): 对于性能问题，用它包裹查找函数来快速测量执行时间。

九、 性能实测 ​

在百万级有序数组中，二分查找相比原生线性查找 (findIndex) 有压倒性优势。

场景: 在 1,000,000 个有序数字中查找一个元素。

方法平均执行时间 (典型 Chrome V8)复杂度
Array.prototype.findIndex~5msO(n)
binarySearch< 0.01msO(log n)

虽然 Map.has 的平均复杂度是 O(1)，但它需要 O(n) 的空间和预处理时间来构建 Map。如果数据天然以有序数组形式存在，且查询频繁，二分查找是最佳选择。

十、 与浏览器原生 API 对照 ​

1. Array.prototype.findIndex(cb) ​

这是最直接的线性查找，复杂度 O(n)，但胜在通用性强，无需排序。

2. Intl.Collator ​

在对字符串数组（特别是多语言）进行二分查找时，应使用 Intl.Collator 作为比较器，它能正确处理复杂的排序规则。

3. Source Map 规范 (ECMA-426) ​

Source Map 本身就是一个与浏览器紧密相关的规范，它定义了编译后代码到源码的映射格式。其核心数据结构"mappings"是一个按编译后行列号排序的 Base64 VLQ 编码字符串。在调试器中，为了根据当前执行位置快速找到对应的源码位置，解析器必须高效地在这个有序映射中查找——这正是二分查找的典型应用场景。因此，ECMA-426 是一个与二分查找强相关的 API 规范。（查看 Source Map 规范）

十一、 Demo 示例 ​

下面是三个从简单到复杂的 TypeScript 二分查找示例，展示了其在不同场景下的应用。

Demo 1: 基础数字查找 ​

这是最标准的二分查找实现，用于在升序排列的数字数组中查找目标值。

typescript

/**
 * 简单二分查找
 * @param arr 有序数组
 * @param target 目标值
 * @returns 目标值的索引，未找到返回 -1
 */
const simpleBinarySearch = (arr: number[], target: number): number => {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    const midValue = arr[mid];

    if (midValue === target) {
      return mid; // 找到了
    } else if (midValue < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // 未找到
}

// --- 使用 ---
const sortedNumbers = [10, 20, 30, 40, 50, 60, 70];
console.log(simpleBinarySearch(sortedNumbers, 40)); // 输出: 3
console.log(simpleBinarySearch(sortedNumbers, 45)); // 输出: -1

解释: 此函数通过迭代不断收缩 [low, high] 闭区间。如果中间值等于目标，则返回索引。如果中间值小于目标，说明目标在右侧，移动 low 指针；反之，移动 high 指针。若循环结束仍未找到，返回 -1。

Demo 2: 支持对象的泛型查找 ​

在实际项目中，我们常常需要查找对象数组。此 Demo 引入了 TypeScript 泛型和自定义比较器，使其能够处理任意类型的有序数据。

typescript
/**
 * 比较器类型
 */
type Comparator<T> = (a: T, b: T) => number;

/**
 * 用户类型
 */
interface User {
  id: number;
  name: string;
}

/**
 * 泛型二分查找
 * @param arr 有序数组
 * @param target 目标值
 * @param comparator 比较器
 * @returns 目标值的索引，未找到返回 -1
 */

const genericBinarySearch = <T>(
  arr: readonly T[],
  target: T,
  comparator: Comparator<T>
): number => {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    const comparison = comparator(arr[mid], target);

    if (comparison === 0) {
      return mid;
    } else if (comparison < 0) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

// --- 使用 ---
const users: User[] = [
  { id: 1, name: 'Alice' },
  { id: 5, name: 'Bob' },
  { id: 12, name: 'Charlie' },
  { id: 16, name: 'David' },
];

const targetUser: User = { id: 12, name: '' }; // 只关心 id

const userComparator: Comparator<User> = (a, b) => a.id - b.id;

console.log(genericBinarySearch(users, targetUser, userComparator)); // 输出: 2

解释: 该函数使用泛型 <T> 使其适用于任何类型。关键在于 comparator 函数，它定义了元素间的排序规则。调用时，我们传入一个比较 id 属性的比较器，从而在 User 对象数组中实现了二分查找。

Demo 3: 变体实现 - Lower Bound ​

lower_bound 是一个非常实用的变体，它用于查找第一个"大于或等于"目标值的元素索引。这在确定插入点等场景中非常有用。

typescript
/**
 * 下界二分查找
 * @param arr 有序数组
 * @param target 目标值
 * @param comparator 比较器
 * @returns 目标值的索引，未找到返回 -1
 */
const lowerBound = <T>(
  arr: readonly T[],
  target: T,
  comparator: (a: T, b: T) => number
): number => {
  let low = 0;
  let high = arr.length; // 注意：high 初始化为数组长度
  let ans = arr.length;

  while (low < high) { // 注意：循环条件是 low < high
    const mid = low + ((high - low) >> 1);
    
    // 如果 mid 元素 >= target，则它可能是答案，
    // 记录下来，并尝试在左边寻找更小的索引
    if (comparator(arr[mid], target) >= 0) {
      ans = mid;
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

// --- 使用 ---
const items = [2, 5, 8, 8, 12, 15];
const numberComparator = (a: number, b: number) => a - b;

// 查找第一个 >= 8 的元素
console.log(lowerBound(items, 8, numberComparator)); // 输出: 2

// 查找第一个 >= 9 的元素 (即 12)
console.log(lowerBound(items, 9, numberComparator)); // 输出: 4

// 查找第一个 >= 1 的元素
console.log(lowerBound(items, 1, numberComparator)); // 输出: 0

// 查找第一个 >= 20 的元素 (不存在，返回插入点)
console.log(lowerBound(items, 20, numberComparator)); // 输出: 6 (数组末尾)

解释: 此实现的精髓在于其循环条件和内部逻辑。当 arr[mid] 大于或等于 target 时，mid 是一个潜在的答案，我们记录它并尝试在左半部分（high = mid）寻找更好的答案。如果 arr[mid] 小于 target，则答案一定在右侧。这种写法的循环最终会收敛到目标位置，即使目标值不存在，也会返回其正确的插入位置。

十二、 真实项目示例 ​

  • Ant Design Table: 在其虚拟化表格中，当用户快速滚动 scroll-bar 时，内部会使用二分查找，根据 scrollTop 值从一个缓存了每行位置信息的数组中，快速定位到应该被渲染的行的起始索引。
  • React Window / React Virtuoso: 这些流行的虚拟列表库，其核心逻辑都依赖于二分查找来计算可视区域内的项目。
  • E-commerce SKU 定价: 假设商品的售价根据购买数量分级（买 10 件 9 折，买 100 件 8 折）。这个价格区间信息可以存成有序数组 [{ quantity: 10, discount: 0.9 }, { quantity: 100, discount: 0.8 }]，通过二分查找的 lower_bound 变体，可以快速找到适用于任意购买数量的折扣。

十三、 扩展阅读 & 练习 ​

1. LeetCode 题目 ​

2. 可视化网站 ​

3. 经典文章 ​

十四 FAQ ​

  • 数据有重复怎么办？
    • 标准实现会返回其中任意一个重复项的索引。如果需要定位第一个或最后一个，需要使用本文提到的变体算法。
  • 可变长对象如何比较？
    • 通过提供自定义的 comparator 函数。该函数接收两个对象 a 和 b，根据你关心的属性（如 a.id, b.id）返回 -1, 0, 1。
  • 为何 mid 用位运算 >> 1？
    • x >> 1 是有符号右移一位，等效于 Math.floor(x / 2)，但通常被认为执行效率更高。在 JS V8 引擎中，这种微优化差异不大，但它是一种简洁且专业的写法。
  • JS 中数字有上限吗，low + high 真的会溢出吗？
    • JS 中的数字是 64 位浮点数（Number），其安全整数范围是 Number.MAX_SAFE_INTEGER (约 9x10¹⁵)。常规数组长度远达不到这个值，所以 JS 中基本不会溢出。但遵循 low + (high - low) / 2 的写法是跨语言的良好编程习惯。