一、二分查找核心原理在有序数组中不断取中间值对比目标值每次舍弃一半区间快速缩小查找范围。适用前提数组单调递增 / 递减优势海量数据查找效率远高于遍历核心变量左边界 left、右边界 right、中间下标 mid二、基础二分模板查找单个目标值#include iostream #include vector using namespace std; // 查找目标值存在返回下标不存在返回-1 int binarySearch(vectorint 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(vectorint 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(vectorint 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 防溢出说明常规写法(leftright)/2数值过大易整型溢出最优写法left (right-left)/2运算安全等价五、经典实战例题例题 1搜索目标元素范围输入有序数组返回目标值起始、结束下标vectorint searchRange(vectorint nums, int target) { int l leftBound(nums, target); int r rightBound(nums, target); return {l, r}; }例题 2搜索插入位置有序数组找到目标插入下标保持数组有序int searchInsert(vectorint 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; }六、二分查找适用场景有序数组元素查找、统计重复个数旋转有序数组搜索找极值、分割区间平方根计算、数值判定类题型大数据量查询优化七、核心边界易错点循环条件left right和left right混用区间截断错误左右边界更新mid±1漏写造成死循环重复元素场景误用基础模板无法取边界查找结束后未校验下标越界八、模板选用口诀唯一元素精准查找 → 基础模板重复元素找最先出现位置 → 左边界模板重复元素找最后出现位置 → 右边界模板无序数组严禁使用二分查找九、今日总结二分依赖有序性时间复杂度\(O(logn)\)熟记基础、左边界、右边界三套模板mid 采用安全写法规避数值溢出边界判断是刷题失分核心点区分不同场景套用模板
