【算法】二分查找算法详解与模板总结：从原理到变体，一篇就够了
目录
二分查找算法详解
二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想是分而治之，每次将搜索范围缩小一半。
基本原理
想象你在查英语字典找"apple"这个词：
- 翻开字典的中间
- 如果这一页的单词在"apple"之前，就往后翻
- 如果这一页的单词在"apple"之后，就往前翻
- 重复这个过程，直到找到"apple"
这就是二分查找的生活例子。
算法步骤
假设有一个升序数组 arr，要查找目标值 target：
- 初始化左指针
left = 0，右指针right = n-1 - 当
left <= right时循环：- 计算中间位置
mid = left + (right - left) / 2（防止整数溢出） - 如果
arr[mid] == target，找到目标，返回mid - 如果
arr[mid] < target，说明目标在右半部分，left = mid + 1 - 如果
arr[mid] > target，说明目标在左半部分，right = mid - 1
- 计算中间位置
- 循环结束未找到，返回 -1
代码实现
基础版本（查找精确值）
intbinarySearch(vector<int>& nums,int target){int left =0;int right = nums.size()-1;while(left <= right){// 避免 (left + right) 可能溢出int mid = left +(right - left)/2;if(nums[mid]== target){return mid;// 找到目标}elseif(nums[mid]< target){ left = mid +1;// 目标在右半部分}else{ right = mid -1;// 目标在左半部分}}return-1;// 未找到}时间复杂度分析
- 时间复杂度：O(log n)
- 每次比较后，搜索范围减半
- 对于大小为 n 的数组，最多需要 log₂(n) 次比较
- 空间复杂度：O(1)
- 只需要常数级别的额外空间
二分查找的变体
1. 查找第一个等于目标的位置
intfindFirst(vector<int>& nums,int target){int left =0, right = nums.size()-1;int result =-1;while(left <= right){int mid = left +(right - left)/2;if(nums[mid]== target){ result = mid;// 记录当前位置 right = mid -1;// 继续向左查找}elseif(nums[mid]< target){ left = mid +1;}else{ right = mid -1;}}return result;}2. 查找最后一个等于目标的位置
intfindLast(vector<int>& nums,int target){int left =0, right = nums.size()-1;int result =-1;while(left <= right){int mid = left +(right - left)/2;if(nums[mid]== target){ result = mid;// 记录当前位置 left = mid +1;// 继续向右查找}elseif(nums[mid]< target){ left = mid +1;}else{ right = mid -1;}}return result;}3. 查找第一个大于等于目标的位置
intfindFirstGreaterOrEqual(vector<int>& nums,int target){int left =0, right = nums.size()-1;while(left <= right){int mid = left +(right - left)/2;if(nums[mid]>= target){ right = mid -1;// 虽然满足条件，但继续向左找更小的}else{ left = mid +1;// 当前太小，向右找}}return left;// left 就是第一个 >= target 的位置}常见应用场景
- 有序数组的查找 - 最基础的应用
- 求平方根 - 在 0 到 x 之间二分查找
- 旋转数组的查找 - 如 [4,5,6,7,0,1,2] 中查找
- 寻找峰值 - 在山峰数组中找到最大值
- 在答案空间二分 - 如"找到最小速度使得在规定时间内完成任务"
注意事项和常见错误
- 循环条件：
left <= rightvsleft < right的选择 - 边界更新：
left = mid + 1和right = mid - 1要正确 - 整数溢出：使用
mid = left + (right - left) / 2而非(left + right) / 2 - 数组必须有序：二分查找的前提是有序，否则结果错误
- 重复元素：处理重复元素时要明确需求（找第一个/最后一个）
二分查找虽然原理简单，但细节容易出错。建议多练习不同类型的题目，熟练掌握各种变体的写法。
二分算法模板总结
//找左边while(left < right){int mid = left +(right - left)/2;//左边if(nums[mid]>= target) right = mid;//右边else left = mid +1;}//找右边while(left < right){int mid = left +(right - left+1)/2;//右边if(nums[mid]<= target) left = mid;//左边else right = mid -1;}实战练习题目（含链接）
⼆分查找（easy）
在排序数组中查找元素的第⼀个和最后⼀个位置（medium）
搜索插⼊位置（easy）
x 的平⽅根（easy）
⼭峰数组的峰顶（easy）
寻找峰值（medium）
搜索旋转排序数组中的最⼩值（medium）
0〜n-1 中缺失的数字（easy）
