二分查找原理与JS实现详解

小伙伴们对文章编程感兴趣吗？是否正在学习相关知识点？如果是，那么本文《二分查找原理及JS实现方法》，就很适合你，本篇文章讲解的知识点主要包括。在之后的文章中也会多多分享相关知识点，希望对大家的知识积累有所帮助！

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

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

解决方案

在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，在某些情况下，比如数组只剩一个元素时，可能会漏掉检查。

再一个就是mid的计算。mid = (left + right) / 2看起来没毛病，但在某些语言（比如Java）中，如果left和right都是非常大的整数，它们的和可能会超过整数的最大表示范围，导致溢出。虽然JavaScript的数字都是浮点数，理论上不会有这种整数溢出的问题，但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实现详解》的详细内容，更多关于的资料请关注golang学习网公众号！