二分查找是一种在已排序数组中高效查找目标值的算法，其核心思想是每次比较中间元素，根据大小关系排除一半的元素，从而将时间复杂度降至o(log n)。它适用于已排序的数据集，广泛应用于字典查找、数据库索引、版本控制（如git bisect）和数值计算等场景。实现时需注意循环条件使用left
二分查找，说白了，就是一种在已排序的数组里找东西的聪明方法。它不是一个一个地挨着找，那样太慢了。它每次都直接跳到中间，看看要找的数是在左边还是右边，然后就把另一半直接扔掉，接着在剩下的一半里继续这个过程。这样一来，每次搜索范围都缩小一半，效率自然就高得吓人。
解决方案
在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
所在的有序区间，来决定是往左边还是右边继续搜索。这需要更精妙的条件判断，但本质上还是在不断缩小搜索范围。
甚至在一些非数值问题中，只要你能找到一个“单调性”——也就是说，问题解空间可以被一分为二，并且其中一半满足某个条件，另一半不满足，你就能用二分查找。比如，寻找满足特定条件的最小/最大值，或者在某个区间内寻找一个“分界点”。这种抽象的思维，才是二分查找最强大、最值得我们学习的地方。它教会我们如何高效地处理那些具有“单调性”的搜索问题。
暂无评论内容