二分查找算法：高效搜索的核心技巧

一、二分查找核心原理

在有序数组中，不断取中间值对比目标值，每次舍弃一半区间，快速缩小查找范围。

• 适用前提：数组单调递增 / 递减
• 优势：海量数据查找效率远高于遍历
• 核心变量：左边界 left、右边界 right、中间下标 mid

二、基础二分模板（查找单个目标值）

#include <iostream> #include <vector> using namespace std; // 查找目标值，存在返回下标，不存在返回-1 int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while(left <= right) { int mid = left + (right - left) / 2; // 防溢出写法 if(nums[mid] == target) { return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }

三、两大边界模板（高频考题）

模板 1：查找左边界（重复元素取最左侧位置）

int leftBound(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; } // 校验下标合法性与数值匹配 if(left >= nums.size() || nums[left] != target) return -1; return left; }

模板 2：查找右边界（重复元素取最右侧位置）

int rightBound(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) left = mid + 1; else right = mid - 1; } if(right < 0 || nums[right] != target) return -1; return right; }

四、mid 防溢出说明

常规写法(left+right)/2，数值过大易整型溢出最优写法：left + (right-left)/2，运算安全等价

五、经典实战例题

例题 1：搜索目标元素范围

输入有序数组，返回目标值起始、结束下标

vector<int> searchRange(vector<int>& nums, int target) { int l = leftBound(nums, target); int r = rightBound(nums, target); return {l, r}; }

例题 2：搜索插入位置

有序数组，找到目标插入下标，保持数组有序

int searchInsert(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) return mid; else if(nums[mid] < target) left = mid + 1; else right = mid - 1; } return left; }

六、二分查找适用场景

1. 有序数组元素查找、统计重复个数
2. 旋转有序数组搜索
3. 找极值、分割区间
4. 平方根计算、数值判定类题型
5. 大数据量查询优化

七、核心边界易错点

1. 循环条件left <= right和left < right混用，区间截断错误
2. 左右边界更新mid±1漏写，造成死循环
3. 重复元素场景，误用基础模板无法取边界
4. 查找结束后，未校验下标越界

八、模板选用口诀

1. 唯一元素精准查找 → 基础模板
2. 重复元素找最先出现位置 → 左边界模板
3. 重复元素找最后出现位置 → 右边界模板
4. 无序数组严禁使用二分查找

九、今日总结

1. 二分依赖有序性，时间复杂度\(O(logn)\)
2. 熟记基础、左边界、右边界三套模板
3. mid 采用安全写法，规避数值溢出
4. 边界判断是刷题失分核心点，区分不同场景套用模板