什么是二分查找？JS如何实现二分查找

<p>二分查找是一种在已排序数组中高效查找目标值的算法，其核心思想是每次比较中间元素，根据大小关系排除一半的元素，从而将时间复杂度降至o(log n)。它适用于已排序的数据集，广泛应用于字典查找、数据库索引、版本控制（如git bisect）和数值计算等场景。实现时需注意循环条件使用left <= right以确保边界覆盖，避免整数溢出的mid = left + (right - left) / 2写法，以及对空数组、单元素数组、目标值不存在等情况的处理。此外，二分查找可扩展用于查找重复元素的第一个或最后一个位置、在旋转排序数组中查找目标值，甚至应用于具有单调性特征的非数值问题，如寻找满足条件的最小值或分界点，体现了其在算法设计中的高效性与思想普适性。</p>

二分查找，说白了，就是一种在已排序的数组里找东西的聪明方法。它不是一个一个地挨着找，那样太慢了。它每次都直接跳到中间，看看要找的数是在左边还是右边，然后就把另一半直接扔掉，接着在剩下的一半里继续这个过程。这样一来，每次搜索范围都缩小一半，效率自然就高得吓人。

解决方案

在JavaScript里实现二分查找，核心思路就是维护一个搜索范围的左右边界，然后不断缩小这个范围直到找到目标或者范围为空。

function binarySearch(arr, target) {
    if (!arr || arr.length === 0) {
        // 数组为空，没得找
        return -1;
    }

    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        // 计算中间索引，这里用这种写法可以避免大数溢出（虽然JS里不常见，但习惯是个好东西）
        const mid = Math.floor(left + (right - left) / 2);

        if (arr[mid] === target) {
            // 找到了，直接返回索引
            return mid;
        } else if (arr[mid] < target) {
            // 中间值比目标小，说明目标在右半部分
            left = mid + 1;
        } else {
            // 中间值比目标大，说明目标在左半部分
            right = mid - 1;
        }
    }

    // 循环结束还没找到，说明目标不存在
    return -1;
}

// 举个例子
const sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log("查找 23:", binarySearch(sortedArray, 23)); // 应该输出 5
console.log("查找 72:", binarySearch(sortedArray, 72)); // 应该输出 8
console.log("查找 100:", binarySearch(sortedArray, 100)); // 应该输出 -1
console.log("查找 2:", binarySearch(sortedArray, 2));   // 应该输出 0
console.log("查找 91:", binarySearch(sortedArray, 91)); // 应该输出 9
console.log("空数组查找:", binarySearch([], 5)); // 应该输出 -1
console.log("单元素数组查找:", binarySearch([7], 7)); // 应该输出 0
console.log("单元素数组查找不存在:", binarySearch([7], 8)); // 应该输出 -1

为什么二分查找如此高效，它的应用场景又有哪些？

你可能觉得，不就是找个数字嘛，挨个遍历不也行？没错，线性查找确实简单粗暴，但想象一下，如果你要在一百万个数字里找一个数，线性查找平均要找五十万次，最坏情况要找一百万次。而二分查找呢？每次砍掉一半，一百万个数字，大概只需要20次左右就能找到（log₂1,000,000 ≈ 19.9）。这效率上的差距，简直是天壤之别！这就是它被称为“O(log n)”时间复杂度的原因，而线性查找是“O(n)”。

它最直接的应用场景，当然就是在大型、已排序的数据集中快速查找特定元素。比如：

• 字典或电话本查找： 你翻字典的时候，是不是也习惯先翻到中间，再决定往前往后？这就是二分查找的思维。
• 数据库索引： 很多数据库内部的数据查找机制，在底层也利用了类似二分查找的思想来加速查询。
• 版本控制系统中的

  git bisect

  登录后复制
  ： 当你想找出是哪个提交引入了bug时，

  git bisect

  登录后复制
  就是利用二分查找的思想，帮你快速定位到那个“坏”提交。
• 数值计算： 比如求一个数的平方根，或者在某个区间内查找满足特定条件的数值，都可以通过二分法来逼近。

所以，只要你的数据是排序好的，或者可以被排序，二分查找几乎总是你优化查找性能的首选。

实现二分查找时，有哪些容易被忽视的细节和常见陷阱？

二分查找看起来简单，但写起来却是个“小坑王”，很多时候一个小细节就能让你调半天。

一个常见的坑是循环条件的设定。到底是

while (left <= right)

while (left < right)

mid

left

right

left <= right

left

right

left < right

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

21

查看详情

再一个就是

mid

mid = (left + right) / 2

left

right

mid = left + (right - left) / 2

还有就是处理边界情况。空数组、只有一个元素的数组、目标值在数组的最左边或最右边、目标值不存在等等，这些都是你需要测试和考虑的。我的代码里对空数组做了初步判断，并用

left = mid + 1

right = mid - 1

left

right

-1

除了基本的查找，二分查找的思想还能如何扩展和变种？

二分查找的魅力，远不止于“找一个数”这么简单。它的核心思想——在有序空间中通过不断减半来缩小搜索范围——可以应用到很多看似不相关的问题上。

一个常见的变种是查找第一个或最后一个出现的重复元素。比如，在一个排好序的数组

[1, 2, 3, 3, 3, 4, 5]

3

3

arr[mid] === target

• 找第一个：

  right = mid - 1

  登录后复制
  ，并记录当前

  mid

  登录后复制
  为一个可能的答案，继续往左找。
• 找最后一个：

  left = mid + 1

  登录后复制
  ，并记录当前

  mid

  登录后复制
  为一个可能的答案，继续往右找。

另一个有意思的扩展是在旋转排序数组中查找。一个原本有序的数组，比如

[0, 1, 2, 4, 5, 6, 7]

[4, 5, 6, 7, 0, 1, 2]

mid

甚至在一些非数值问题中，只要你能找到一个“单调性”——也就是说，问题解空间可以被一分为二，并且其中一半满足某个条件，另一半不满足，你就能用二分查找。比如，寻找满足特定条件的最小/最大值，或者在某个区间内寻找一个“分界点”。这种抽象的思维，才是二分查找最强大、最值得我们学习的地方。它教会我们如何高效地处理那些具有“单调性”的搜索问题。

以上就是什么是二分查找？JS如何实现二分查找的详细内容，更多请关注php中文网其它相关文章！