深入掌握 JavaScript 二分查找：从原理到实战的完整指南

2026-02-07 07:38:15 0条评论 3次阅读 0人点赞

作为一名开发者，我们经常需要在海量的数据中快速定位到那个特定的“目标”。想象一下，如果数据已经排好了序，我们还需要像线性查找那样，一个个地去比对吗？当然不！今天，我们将一起深入探讨一种极具效率的算法——二分查找。在这篇文章中，我们不仅要理解它的核心逻辑，还要通过多种 JavaScript 实现方式，看看它究竟是如何在 O(logN) 的时间复杂度内完成搜索的。此外，我还会分享一些在实际开发中可能遇到的“坑”以及优化技巧。准备好了吗？让我们开始这场算法的探索之旅吧。

为什么选择二分查找？

在我们深入代码之前，先来聊聊为什么我们要学习这个算法。你可能已经知道，线性查找的时间复杂度是 O(N)，这意味着如果数据量增加一倍，查找时间可能也会增加一倍。而二分查找则完全不同，它的前提非常简单：数组必须是有序的。

利用这个“有序”的特性，我们可以采用一种“分而治之”的策略。每次查找，我们都会排除掉一半的数据。这种指数级的收敛速度，使得它在大规模数据查找中表现得异常出色。

让我们看看具体的输入输出示例：

// 输入 : arr[] = {1, 3, 5, 7, 8, 9}, x = 5
// 输出 : 找到元素！

// 输入 : arr[] = {1, 3, 5, 7, 8, 9}, x = 6
// 输出 : 未找到元素！

请注意，接下来的所有讨论都基于一个重要的假设：数组已经排序。

核心逻辑：分而治之的艺术

二分查找的核心思想其实非常直观。假设我们在字典里查一个单词，我们不会从第一页开始翻，而是直接翻到中间。如果我们要找的单词比中间页的单词拼法靠前，我们就只看左半部分；反之，则看右半部分。在代码中，这个过程也是一样的。

我们将通过两种主要的方式来实现它：递归和迭代。

方法一：递归实现

递归是一种优雅的解决问题的思路，它将大问题分解为小问题。在二分查找中，递归的实现非常符合逻辑。

#### 算法步骤

  • 基本条件（Base Case）： 首先检查我们的搜索范围是否有效。如果起始索引 INLINECODE51adc888 大于结束索引 INLINECODE31e64f48，说明搜索空间已经耗尽，元素不存在，返回 false。
  • 寻找中点： 计算当前搜索范围的中间索引 mid。
  • 比较与判断：

* 如果 INLINECODE48a5295b 正好等于我们要找的 INLINECODEc6a0b5f3，恭喜，直接返回 true。

* 如果 INLINECODEc685c687 比 INLINECODEec2a51bd 大，说明目标只能在左半边。我们以 end = mid - 1 为新边界，递归调用函数。

* 如果 INLINECODE562ef8b3 比 INLINECODEb957d510 小，说明目标只能在右半边。我们以 start = mid + 1 为新边界，递归调用函数。

#### 代码示例

下面是一个完整的递归实现，让我们仔细看看代码是如何工作的：

/**
 * 递归方式的二分查找
 * @param {number[]} arr - 已排序的数组
 * @param {number} x - 目标元素
 * @param {number} start - 当前搜索范围的起始索引
 * @param {number} end - 当前搜索范围的结束索引
 * @returns {boolean} - 是否找到目标元素
 */
let recursiveFunction = function (arr, x, start, end) {

    // 基本条件：如果起始索引超过了结束索引，说明没找到
    if (start > end) return false;

    // 计算中间索引
    // 使用 Math.floor 确保得到整数索引
    let mid = Math.floor((start + end) / 2);

    // 检查中间元素是否就是我们要找的 x
    if (arr[mid] === x) return true;

    // 如果中间元素大于 x
    // 说明 x 只可能在左半部分（即索引较小的部分）
    if (arr[mid] > x)
        return recursiveFunction(arr, x, start, mid - 1);
    else 
        // 如果中间元素小于 x
        // 说明 x 只可能在右半部分（即索引较大的部分）
        return recursiveFunction(arr, x, mid + 1, end);
}

// 驱动代码：让我们测试一下
let arr = [1, 3, 5, 7, 8, 9];
let x = 5;

if (recursiveFunction(arr, x, 0, arr.length - 1)) {
    console.log("元素已找到！");
}
else { 
    console.log("未找到元素！"); 
}

// 测试一个不存在的元素
x = 6;

if (recursiveFunction(arr, x, 0, arr.length - 1)) {
    console.log("元素已找到！");
}
else { 
    console.log("未找到元素！"); 
}

#### 复杂度分析

  • 时间复杂度： O(logN)。每次递归调用都将问题规模减半。
  • 辅助空间： O(logN)。这是递归调用栈的空间。虽然我们在代码中没有显式地创建数据结构，但计算机需要内存来记录每一层递归的返回地址和局部变量。

方法二：迭代实现

虽然递归代码很优雅，但在 JavaScript 中，过多的递归调用有时会导致调用栈溢出，或者在某些引擎中性能略逊于循环。因此，掌握迭代法是至关重要的。我们不使用函数自己调用自己，而是使用一个 while 循环来不断地缩小搜索范围。

#### 算法步骤

  • 初始化 INLINECODE646d1d74 和 INLINECODEd145688c。
  • 只要 start <= end，就继续循环。
  • 在循环内部，计算 mid。
  • 如果 INLINECODEd2d476f6，返回 INLINECODE00c1cea2。
  • 如果 INLINECODEe244d865，调整 INLINECODE21294dda（向右找）。
  • 否则，调整 end = mid - 1（向左找）。
  • 如果循环结束还没返回，说明没找到，返回 false。

#### 代码示例

这个版本通常是生产环境中的首选，因为它没有额外的栈空间消耗。

/**
 * 迭代方式的二分查找
 * @param {number[]} arr - 已排序的数组
 * @param {number} x - 目标元素
 * @returns {boolean} - 是否找到目标元素
 */
let iterativeFunction = function (arr, x) {

    let start = 0, end = arr.length - 1;

    // 当 start 没有遇到 end 时，我们继续在缩小范围内迭代
    while (start <= end) {

        // 找到中间索引
        let mid = Math.floor((start + end) / 2);

        // 如果中间位置正好是我们要找的元素
        if (arr[mid] === x) return true;

        // 如果中间元素小于 x
        // 说明目标在右半部分，我们将起始点移到 mid + 1
        else if (arr[mid] < x)
            start = mid + 1;
        
        // 如果中间元素大于 x
        // 说明目标在左半部分，我们将结束点移到 mid - 1
        else
            end = mid - 1;
    }

    // 如果循环结束还没找到，返回 false
    return false;
}

// 驱动代码
let arr = [1, 3, 5, 7, 8, 9];
let x = 5;

if (iterativeFunction(arr, x)) {
    console.log("元素已找到！");
}
else {
    console.log("未找到元素！");
}

x = 8;

if (iterativeFunction(arr, x)) {
    console.log("元素已找到！");
}
else {
    console.log("未找到元素！");
}

#### 复杂度分析

  • 时间复杂度： O(logN)。和递归一样，我们也是每次排除一半的数据。
  • 辅助空间： O(1)。这里我们只用了几个变量（INLINECODE34f92b56, INLINECODEfcd00cbd, mid），没有额外的内存开销，这是迭代法的巨大优势。

进阶实战：在对象数组中查找

上面的例子都是基于纯数字数组的，但在实际的前端开发中，我们经常需要处理对象数组。比如，我们有一个用户列表，想根据 ID 快速找到用户对象。二分查找的逻辑是一样的，只是比较的方式变了。

假设我们有一个根据 id 排序的用户数组：

// 示例数据：根据 id 排序的用户对象数组
const users = [
    { id: 101, name: "Alice" },
    { id: 203, name: "Bob" },
    { id: 350, name: "Charlie" },
    { id: 404, name: "David" },
    { id: 599, name: "Eve" }
];

/**
 * 在对象数组中进行二分查找
 * @param {Array} arr - 已排序的对象数组
 * @param {number} targetId - 要查找的目标 ID
 */
function searchUserById(arr, targetId) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);
        const midId = arr[mid].id; // 注意这里：我们比较的是对象的 id 属性

        if (midId === targetId) {
            return arr[mid]; // 返回找到的用户对象
        } else if (midId < targetId) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return null; // 未找到返回 null
}

// 测试查找 ID 为 350 的用户
const result = searchUserById(users, 350);
if (result) {
    console.log(`找到用户: ${result.name}`);
} else {
    console.log("用户不存在");
}

常见陷阱：整数溢出问题

在计算中间索引 INLINECODE3272caae 时，我们通常写成 INLINECODEd83268b2。在 JavaScript 中，由于数字类型是 IEEE 754 双精度浮点数，处理极大整数时精度可能会丢失，但更重要的是在其他强类型语言（如 Java 或 C++）中，如果 INLINECODEa0247bcf 和 INLINECODEea331149 都非常大，INLINECODE9749330b 可能会超过整型的最大值，导致整数溢出，从而得到一个负数的 INLINECODE3267769c，引发程序崩溃。

最佳实践： 虽然在 JavaScript 中直接溢出导致崩溃的情况较少见，但为了严谨和跨语言的通用性，我们建议使用以下公式计算中点：

// 推荐写法：防止溢出
let mid = Math.floor(start + (end - start) / 2);

这种写法先计算差值，再除以 2，最后加上起始值，永远不会有溢出的风险。

性能优化建议

  • 尽量使用迭代法： 除非你的数据规模非常小，否则优先选择 while 循环的实现方式。它避免了函数调用的开销，也不会因为递归深度过大而栈溢出。
  • 预排序： 二分查找的前提是数组有序。如果你的数据是动态增加的，每次插入后排序的成本是 O(N)。如果你需要频繁插入和查找，可能需要考虑平衡二叉搜索树之类的数据结构。但在静态数据或极少变更的数据场景下，先排序一次，然后多次二分查找，是最划算的。
  • 返回索引而非布尔值： 在实际业务中，我们往往不仅想知道“存不存在”，更想知道“它在哪里”。你可以很容易地修改上述代码，将返回值从 INLINECODE70f8ac0d 改为 INLINECODE00214944 或 -1。

返回索引的优化版示例

让我们把迭代方法改造成返回索引的版本，这会更有用：

/**
 * 返回目标元素索引的二分查找
 * @returns {number} 目标元素的索引，未找到返回 -1
 */
function binarySearchIndex(arr, x) {
    let start = 0, end = arr.length - 1;

    while (start <= end) {
        // 使用防溢出的写法
        let mid = Math.floor(start + (end - start) / 2);

        if (arr[mid] === x) return mid;
        
        if (arr[mid] < x)
            start = mid + 1;
        else
            end = mid - 1;
    }

    return -1;
}

let arr = [10, 20, 30, 40, 50];
let target = 30;
let index = binarySearchIndex(arr, target);

if (index !== -1) {
    console.log(`元素 ${target} 位于索引 ${index}`);
} else {
    console.log("元素未找到");
}

总结

在这篇文章中，我们像探险一样，从简单的线性搜索对比出发，一步步解析了二分查找的奥秘。我们学习了如何用递归和迭代两种方式在 JavaScript 中实现它，并进一步探讨了如何在对象数组中应用这一逻辑。同时，我们也触及了整数溢出这一潜在的陷阱以及如何通过更安全的数学公式来规避它。

掌握二分查找，不仅仅是背诵一段代码，更是理解“如何通过利用数据的额外特性（有序性）来换取性能上的巨大提升”这一思维方式。下次当你面对一个有序的大数据集时，希望你能自信地运用二分查找，让你的代码运行得飞快。

现在，打开你的控制台，试着写一段属于你自己的二分查找代码吧！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/31142.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年