二分查找算法详解：高效搜索的“分治神器”，一文搞懂原理与实战！
创作时间:
作者:
@小白创作中心
二分查找算法详解：高效搜索的“分治神器”，一文搞懂原理与实战！
引用
CSDN
1.
https://blog.csdn.net/WD1213484/article/details/146919694
二分查找算法是一种在有序数组中高效查找目标值的算法，其核心思想是每次将查找区间缩小一半，从而快速定位目标值。本文将从算法原理、代码实现、关键点解析、复杂度分析、优化思路以及应用场景等多个方面，帮助读者全面理解二分查找算法。
二分查找是一种在有序数组中高效查找目标值的算法，其核心思想是每次将查找区间缩小一半，从而快速定位目标值。比如猜数字游戏：想一个 1 - 100 的数字，每次猜中间值（50），根据 “大了” 或 “小了” 的提示缩小范围，最多 7 次必中。
1.1 核心步骤
- 确定范围：初始化左边界 left = 0，右边界 right = 数组长度 - 1。
- 计算中间值：mid = left + Math.floor ((right - left)/2)（防溢出写法）。
- 比较判断：若 nums[mid] === target，返回 mid；若 nums[mid] > target，更新 right = mid - 1；若 nums[mid] < target，更新 left = mid + 1。
- 循环终止：当 left > right 时，返回 - 1。
关键在于每次比较后都能排除一半的元素，大大减少了查找的次数，这使得二分查找的时间复杂度仅为 O (log n)，其中 n 是数组的长度。
二、代码实现：从基础到优化
了解原理后，来看 JavaScript 代码实现，包括非递归和递归两种方式。
2.1 非递归实现（推荐）
非递归方式使用 while 循环实现，更高效，代码如下：
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
// 防溢出写法
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
// 测试
let array = [1, 3, 5, 7, 9, 11, 13, 15];
let targetNumber = 7;
console.log(binarySearch(array, targetNumber));
代码解释：
- 初始化左边界 left 为 0，右边界 right 为数组长度减 1。
- 在 while 循环中，只要 left <= right 就继续查找。
- 每次计算中间位置 mid，使用 left + Math.floor ((right - left)/2) 防溢出。
- 根据 arr[mid] 与 target 的比较结果更新 left 或 right。
- 若循环结束仍未找到，返回 - 1。
2.2 递归实现（简洁但需注意栈溢出）
递归实现代码更简洁，但可能因递归深度过大导致栈溢出，适用于小数据量，代码如下：
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) {
return -1;
}
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
return binarySearchRecursive(arr, target, left, mid - 1);
} else {
return binarySearchRecursive(arr, target, mid + 1, right);
}
}
// 测试
let array = [1, 3, 5, 7, 9, 11, 13, 15];
let targetNumber = 11;
console.log(binarySearchRecursive(array, targetNumber));
代码解释：
- 递归函数接收数组 arr、目标值 target、左边界 left（默认 0）和右边界 right（默认数组长度减 1）。
- 若 left > right，说明未找到，返回 - 1。
- 计算中间位置 mid。
- 根据 arr[mid] 与 target 的比较结果，递归调用函数在左半部分或右半部分查找。
三、关键点解析：避免常见错误
二分查找虽思路简单，但实际编码时需注意一些细节，避免常见错误。
3.1 必须有序数组
二分查找的前提是数组有序，无序数组无法使用该算法。若遇到无序数组，需先排序，如使用 JavaScript 的 Array.sort() 方法，示例如下：
let unorderedArray = [5, 3, 7, 1, 9];
unorderedArray.sort((a, b) => a - b);
console.log(unorderedArray);
3.2 中间值计算防溢出
传统计算中间值的写法 (left + right) / 2，当 left 和 right 很大时，可能导致整数溢出。改进方法是使用 left + Math.floor((right - left)/2)，这样更安全，如：
let left = 1000000000;
let right = 2000000000;
// 传统写法可能溢出
let mid1 = (left + right) / 2;
// 安全写法
let mid2 = left + Math.floor((right - left) / 2);
console.log(mid2);
3.3 循环条件与边界处理
- 循环条件：使用 left <= right 作为循环条件，能确保最后一个元素也被检查到。若用 left < right，当 left 等于 right 时，循环提前结束，可能遗漏目标值。
- 边界更新：比较后更新边界时，right = mid - 1 和 left = mid + 1 能避免重复比较已检查过的 mid 位置元素。例如，若不更新 right，下次循环可能再次比较 mid 位置元素，降低效率 。
四、复杂度分析：为什么是 O (log n)
二分查找的复杂度分析从时间、空间和稳定性三个维度进行。
4.1 时间复杂度
二分查找每次比较都能排除一半元素，因此时间复杂度为 O (log n)。推导过程如下：
- 假设数组长度为 n，最多需要比较 f (n) 次找到目标元素。
- 当 n = 1 时，f (1) = 1 （只需比较 1 次）。
- 当 n > 1 时，f (n) = 1 + f (n/2) （每次比较 1 次，然后在一半的数组中查找）。
- 递推可得 f (n) = log n + 1 ，忽略常数 1 后，时间复杂度为 O (log n) 。
4.2 空间复杂度
- 非递归：仅使用常数级别的额外空间（left、right、mid 等变量），空间复杂度为 O (1)。
- 递归：递归调用会使用栈空间，递归深度最大为 log n，因此空间复杂度为 O (log n) 。
4.3 稳定性
二分查找过程中不涉及元素交换，因此稳定性取决于原数组。若原数组是有序且稳定的，二分查找结果也是稳定的 。
五、优化思路：拓展应用场景
二分查找在实际应用中，除了基础的查找功能，还可以通过一些优化思路来处理更复杂的情况。
5.1 查找第一个 / 最后一个出现的位置
当数组中存在重复元素时，有时需要找到目标值第一个或最后一个出现的位置。以查找第一个出现的位置为例，实现代码如下：
function findFirstOccurrence(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
// 如果mid是第一个元素或者前一个元素不等于target，说明找到第一个位置
if (mid === 0 || arr[mid - 1]!== target) {
return mid;
} else {
// 否则继续在左半部分查找
right = mid - 1;
}
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
// 测试
let array = [1, 3, 3, 3, 5, 7, 9];
let targetNumber = 3;
console.log(findFirstOccurrence(array, targetNumber));
查找最后一个出现的位置同理，只需在找到目标值后，将左边界更新为 mid + 1 继续在右半部分查找。
5.2 处理重复元素
当数组存在重复元素时，除了上述查找第一个和最后一个位置的方法，还可以通过扩展左右边界或两次二分确定范围。例如，在找到目标值后，向左右两边扩展，找到所有相同元素的范围。
function findAllOccurrences(arr, target) {
let left = 0;
let right = arr.length - 1;
let result = [];
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
let i = mid;
let j = mid;
// 向左扩展
while (i >= 0 && arr[i] === target) {
result.push(i);
i--;
}
// 向右扩展
while (j < arr.length && arr[j] === target) {
result.push(j);
j++;
}
return result;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
// 测试
let array = [1, 3, 3, 3, 5, 7, 9];
let targetNumber = 3;
console.log(findAllOccurrences(array, targetNumber));
5.3 旋转数组中的查找
对于旋转数组（如 [4,5,6,7,0,1,2]），也可以使用二分查找。关键在于判断哪一半是有序的，然后根据目标值与有序部分的关系缩小查找范围。代码如下：
function searchRotatedArray(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
return mid;
}
// 左半部分有序
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 右半部分有序
else {
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// 测试
let array = [4, 5, 6, 7, 0, 1, 2];
let targetNumber = 0;
console.log(searchRotatedArray(array, targetNumber));
这样，通过这些优化思路，二分查找算法能够在更多复杂场景中发挥作用，提升查找效率和应用范围。
六、应用场景：实际开发中的用武之地
二分查找算法在许多实际场景中都有广泛应用，因其高效的查找特性，大大提升了数据处理的效率。
- 数据库索引：在数据库中，索引通常是有序的，二分查找可以快速定位到特定记录。例如在用户表中根据用户 ID 查找用户信息，数据库会先对用户 ID 建立索引，然后使用二分查找在索引中快速定位到对应的记录，从而提高查询效率。假设数据库中有 100 万条用户记录，若使用线性查找平均需要查找 50 万次，而二分查找最多只需 20 次（log₂1000000 ≈ 20）。
- 文件系统：文件系统中，文件路径或文件名列表可能是有序存储的，二分查找可用于快速查找文件。比如在一个包含大量文件的文件夹中，通过文件名查找特定文件时，操作系统可利用二分查找迅速定位，节省查找时间。
- 游戏开发：在游戏中，若有排序后的对象列表，如按距离玩家远近排序的怪物列表，使用二分查找能快速搜索到特定怪物，提升游戏运行效率。例如在一个大型多人在线游戏中，可能同时存在上千个怪物，使用二分查找可以快速定位到距离玩家最近的怪物，优化游戏性能 。
- 算法竞赛：二分查找是算法竞赛中的常见考点，常用于解决 “查找插入位置”“旋转数组最小值” 等问题。例如 LeetCode 上的 “搜索插入位置” 问题，给定一个排序数组和目标值，若目标值不存在，需返回其将被插入的位置，使用二分查找可高效解决 。
在实际开发中，二分查找的应用远不止这些，它为各种需要快速查找数据的场景提供了高效解决方案，是开发者不可或缺的工具。
七、总结：掌握分治思想，提升效率
二分查找通过分治策略实现高效搜索，是算法中的经典工具。虽然简单，但细节易错，需注意边界条件和溢出问题。掌握其原理后，可进一步探索旋转数组、重复元素处理等进阶场景。快去试试把代码复制到你的开发环境中，直观感受二分查找的执行过程吧！
热门推荐
准备长期健身，有哪些忠告？
吕布貂蝉阵容搭配推荐(吕布貂蝉搭配什么阵容最好)
法拍房价格一高一低？该如何精准评估真实价值？
什么是人性
什么是强化底盘
疾驰逐梦，创造中国速度
春节宅家必读，肺结节、肺癌消融后，这5类“年货”要谨慎
液化气安全培训：掌握关键技能，确保操作无忧
朋友结婚什么时候送花好？婚礼送花指南，让你的祝福不迟到
腰椎管狭窄症不做手术能治好吗
六十四卦雷风恒卦详解：恒卦爻辞的作用
水质站房式在线监测系统集方案要点
气瓶仓库安全管理要求是什么
网线的粗细和传输速率有关系吗？6类线为什么比超5类线速率快
牛首山景区概况：自然风光与人文底蕴的完美融合
睡不着觉的解决方法有哪些
公证文书的法律效力
关于禅的入门，这5本书值得一读
智能辅助驾驶系统解析：让驾驶更轻松安全
间歇性禁食对减肥有效且有助健康，3种方法了解下~
低碳水减肥法：原理、实施步骤与注意事项
最常用的支气管扩张吸入剂
400系列不锈钢概述
市面上常见的快充协议大盘点：各品牌快充技术详解
这届年轻人喜欢“深度游”香港
让“绿色”成为发展的活力和底色
公众与环保如何“零距离”？成都积极探索环保设施向公众开放
如何获得美国全额奖学金留学的机会
小针刀怎么治腰椎管狭窄
科学家揭示高温超导本质，为争论30年的高温超导理论提供答案