二分查找——算法总结与教学指南

📚 算法核心思想

二分查找的本质

• 在有序集合中通过不断折半缩小搜索范围
• 每次比较都能排除一半的错误答案
• 核心前提：数据必须有序（直接或间接）

三种二分查找模式

🔧 通用解题框架

基础二分查找模板

intbinarySearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;// 防止溢出if(nums[mid]==target){returnmid;// 找到目标}elseif(nums[mid]<target){left=mid+1;// 搜索右半部分}else{right=mid-1;// 搜索左半部分}}return-1;// 未找到}

寻找边界的二分模板

// 寻找第一个 >= target 的位置（lower_bound）intfindFirstGreaterOrEqual(vector<int>&nums,inttarget){intleft=0,right=nums.size();// 注意：右开区间while(left<right){intmid=left+(right-left)/2;if(nums[mid]>=target){right=mid;// 保留mid，继续向左找}else{left=mid+1;// 向右找}}returnleft;// 第一个 >= target 的位置}

🎯 问题识别技巧

什么时候用二分查找？

1. 明显关键词：有序、排序、搜索、查找
2. 数据规模大：O(n) 会超时，需要 O(log n)
3. 答案单调性：条件满足性随参数单调变化

判断依据

// 如果是这些问题，考虑二分查找：-"在排序数组中查找元素的第一个和最后一个位置"-"寻找旋转排序数组中的最小值"-"在 D 天内送达包裹的能力"（最优化问题）-"制作 m 束花所需的最少天数"-"分割数组的最大值"

🔍 关键决策点

1. 如何选择区间表示？

• 左闭右闭[left, right]：while(left <= right)，更新时mid±1
• 左闭右开[left, right)：while(left < right)，更新时left=mid+1或right=mid

2. 如何判断搜索方向？

// 不同问题的判断条件if(nums[mid]==target)// 标准查找if(nums[mid]>=target)// 寻找左边界if(nums[mid]>target)// 寻找右边界if(canFinish(piles,mid,h))// 最优化问题（抽象条件）

3. 如何避免死循环？

• 确保每次循环区间都在缩小
• 注意mid的计算方式：mid = left + (right-left)/2（向下取整）
• 更新边界时至少移动一步：left = mid+1或right = mid-1

💡 经典问题分类与解法

类型1：精确查找

// 问题：在排序数组中查找目标值intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;elseif(nums[mid]<target)left=mid+1;elseright=mid-1;}return-1;}

类型2：寻找边界

// 问题：在排序数组中查找元素的第一个和最后一个位置vector<int>searchRange(vector<int>&nums,inttarget){// 找左边界：第一个 >= target 的位置intleft=lower_bound(nums.begin(),nums.end(),target)-nums.begin();// 找右边界：第一个 > target 的位置 - 1intright=upper_bound(nums.begin(),nums.end(),target)-nums.begin()-1;if(left<=right)return{left,right};return{-1,-1};}

类型3：旋转数组查找

// 问题：搜索旋转排序数组intsearchRotated(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;// 判断哪一部分是有序的if(nums[left]<=nums[mid]){// 左半部分有序if(nums[left]<=target&&target<nums[mid]){right=mid-1;// 目标在有序的左半部分}else{left=mid+1;// 目标在右半部分}}else{// 右半部分有序if(nums[mid]<target&&target<=nums[right]){left=mid+1;// 目标在有序的右半部分}else{right=mid-1;// 目标在左半部分}}}return-1;}

类型4：最优化问题（抽象二分）

// 问题：在 D 天内送达包裹的能力intshipWithinDays(vector<int>&weights,intdays){// 确定二分搜索边界intleft=*max_element(weights.begin(),weights.end());// 最小能力intright=accumulate(weights.begin(),weights.end(),0);// 最大能力while(left<right){intmid=left+(right-left)/2;if(canShip(weights,days,mid)){right=mid;// 尝试更小的能力}else{left=mid+1;// 需要更大的能力}}returnleft;}boolcanShip(vector<int>&weights,intdays,intcapacity){intcurrent=0,needed=1;for(intweight:weights){if(current+weight>capacity){needed++;current=0;}current+=weight;}returnneeded<=days;}

🚀 教学要点

给初学者的建议

1. 从理解原理开始

   二分查找为什么是 O(log n)？ 每次比较排除一半元素 → 最多 log₂n 次

2. 掌握两种模板

   • 模板1：精确查找（闭区间）
   • 模板2：边界查找（左闭右开）

3. 手动模拟过程

   数组：[1,3,5,7,9,11]查找：7步骤1：left=0,right=5,mid=2,nums[2]=5<7→ left=3步骤2：left=3,right=5,mid=4,nums[4]=9>7→ right=3步骤3：left=3,right=3,mid=3,nums[3]=7==7→ 找到

4. 注意常见陷阱

   • 整数溢出：使用mid = left + (right-left)/2
   • 死循环：确保每次循环边界都在变化
   • 边界条件：空数组、单个元素、目标不存在

二分查找的思维转换

1. 从"找答案"到"猜答案+验证"

   传统：直接找到正确答案 二分：猜一个答案 → 验证是否正确 → 调整猜测

2. 判定函数的编写

   // 最优化问题的关键：编写判定函数boolisValid(intguess){// 判断 guess 是否满足条件// 通常需要 O(n) 或 O(m) 的验证}

练习题进阶路径

Level 1: 基础二分查找（704题） Level 2: 寻找边界（34题） Level 3: 旋转数组搜索（33、81题） Level 4: 抽象二分查找（875、1011题） Level 5: 二维二分查找（74、240题） Level 6: 复杂最优化问题（410、1231题）

📝 一句话总结各类问题

1. 标准二分：有序数组中找目标值
2. 寻找边界：lower_bound和upper_bound的运用
3. 旋转数组：先判断哪边有序，再决定搜索方向
4. 峰值查找：比较 mid 和 mid+1，向更高的方向搜索
5. 最优化问题：二分搜索答案，编写判定函数验证
6. 二维二分：将二维映射到一维，或行列分别二分

🎁 终极心法

二分查找 = 有序数据 + 折半排除 + 边界处理

四步解题法

1. 判断是否能用二分：数据是否有序？答案是否有单调性？
2. 确定搜索范围：最小可能值和最大可能值是什么？
3. 编写判定函数：如何验证一个猜测值是否可行？
4. 处理边界情况：空数组、找不到、重复元素等

调试技巧

// 在循环中添加打印，观察搜索过程while(left<=right){intmid=left+(right-left)/2;cout<<"left="<<left<<", right="<<right<<", mid="<<mid<<", nums[mid]="<<nums[mid]<<endl;// ...}

掌握二分查找的关键在于理解其"减而治之"的思想，并通过大量练习熟悉各种变体。从标准二分开始，逐步挑战更复杂的问题，最终能够灵活运用二分思想解决各类最优化问题。