【算法】二分查找算法详解与模板总结：从原理到变体，一篇就够了

目录

• 二分查找算法详解
  • 基本原理
  • 算法步骤
  • 代码实现
    • 基础版本（查找精确值）
  • 时间复杂度分析
  • 二分查找的变体
    • 1. 查找第一个等于目标的位置
    • 2. 查找最后一个等于目标的位置
    • 3. 查找第一个大于等于目标的位置
  • 常见应用场景
  • 注意事项和常见错误
• 二分算法模板总结
• 实战练习题目（含链接）

二分查找算法详解

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想是分而治之，每次将搜索范围缩小一半。

基本原理

想象你在查英语字典找"apple"这个词：

1. 翻开字典的中间
2. 如果这一页的单词在"apple"之前，就往后翻
3. 如果这一页的单词在"apple"之后，就往前翻
4. 重复这个过程，直到找到"apple"

这就是二分查找的生活例子。

算法步骤

假设有一个升序数组 arr，要查找目标值 target：

1. 初始化左指针 left = 0，右指针 right = n-1
2. 当 left <= right 时循环：
   • 计算中间位置 mid = left + (right - left) / 2（防止整数溢出）
   • 如果 arr[mid] == target，找到目标，返回 mid
   • 如果 arr[mid] < target，说明目标在右半部分，left = mid + 1
   • 如果 arr[mid] > target，说明目标在左半部分，right = mid - 1
3. 循环结束未找到，返回 -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 的位置}

常见应用场景

1. 有序数组的查找 - 最基础的应用
2. 求平方根 - 在 0 到 x 之间二分查找
3. 旋转数组的查找 - 如 [4,5,6,7,0,1,2] 中查找
4. 寻找峰值 - 在山峰数组中找到最大值
5. 在答案空间二分 - 如"找到最小速度使得在规定时间内完成任务"

注意事项和常见错误

1. 循环条件：left <= right vs left < right 的选择
2. 边界更新：left = mid + 1 和 right = mid - 1 要正确
3. 整数溢出：使用 mid = left + (right - left) / 2 而非 (left + right) / 2
4. 数组必须有序：二分查找的前提是有序，否则结果错误
5. 重复元素：处理重复元素时要明确需求（找第一个/最后一个）

二分查找虽然原理简单，但细节容易出错。建议多练习不同类型的题目，熟练掌握各种变体的写法。

二分算法模板总结

//找左边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）