SYSTEM
二分查找
src/content/notes/algorithm/二分查找.md 统一前置:二分通用规范(全部背住)
全部使用:左闭右闭 [left, right]
循环条件:left <= right
防溢出mid:mid = left + (right - left) / 2
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 防溢出,不要写 (left + right) / 2
int mid = left + (right - left) / 2;
}
二分只有两种思维:
- 找数:相等直接返回
- 找边界/找答案:相等不返回,继续缩区间
核心区分标准:
- 找到目标直接返回:基础精确查找
- 找到目标不返回,收缩区间:查找左右边界
- 数组分段有序:旋转数组二分
- 不在数组找元素,求最值解:二分答案
变式一:基础二分(精确查找 / 插入位置)
经典题:LC35 搜索插入位置
题目极简说明:给定一个无重复升序数组和目标值,有目标返回下标,没有就返回应该插入的位置。
题型特征:最标准有序数组、无重复、只需要找位置。
核心思路:
命中 → 直接返回mid
mid小了 → 右找 left=mid+1
mid大了 → 左找 right=mid-1
完整模板
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 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即是答案。
变式二:边界二分(重复数组找首尾)
经典题:LC34 在排序数组中查找元素的第一个和最后一个位置
题目极简说明:有序但有重复数组,找出目标值的「最左下标」和「最右下标」,没有就返回[-1,-1]。
题型特征:有重复元素,不能找到就停,必须压到边界。
核心坑点:等于target不返回!继续收缩区间
左边界(第一个target):命中时 right = mid - 1(往左逼)
右边界(最后一个target):命中时 left = mid + 1(往右逼)
// 找左边界
if(nums[mid] == target){
ans = mid;
right = mid - 1;
}
// 找右边界
if(nums[mid] == target){
ans = mid;
left = mid + 1;
}
完整模板
public int[] searchRange(int[] nums, int target) {
int l = findLeft(nums, target);
int r = findRight(nums, target);
return new int[]{l, r};
}
// 找左边界
private int findLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
ans = mid;
right = mid - 1;
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return ans;
}
// 找右边界
private int findRight(int[] nums, int target) {
int left = 0, right = nums.length - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
ans = mid;
left = mid + 1;
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return ans;
}
一句话总结:重复数组找区间,相等不停止,向内挤压找极限。
变式三:旋转数组二分(局部有序)
分支1:LC33 搜索旋转排序数组
题目极简说明:升序数组旋转一次(如 [4,5,6,7,0,1,2]),无重复,找目标值下标。
题型特征:整体无序、左右必有一段有序。
核心思路固定套路:
- 先看左边是否有序(nums[left] <= nums[mid])
- 看 target 在不在有序区间内 → 在就搜有序侧,不在就搜另一侧
1 nums[left] <= nums[mid] → 左区间有序
- target 落在
[nums[left], nums[mid]]:右边界左移right=mid-1 - 否则去右区间查找
left=mid+1
-
右区间有序
- target 落在
[nums[mid], nums[right]]:左边界右移left=mid+1 - 否则去左区间查找
right=mid-1
- target 落在
if(nums[mid] == target) return mid;
// 左段有序
if(nums[left] <= nums[mid]){
if(target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
}else{
// 右段有序
if(target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
完整模板
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}
if(nums[left] <= nums[mid]){
if(target >= nums[left] && target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}else{
if(target > nums[mid] && target <= nums[right]){
left = mid + 1;
}else{
right = mid -1;
}
}
}
return -1;
}
}
分支2:LC153 寻找旋转排序数组最小值
题目极简说明:旋转升序数组,找最小值。
核心超简口诀:只比 mid 和 right
mid值大 → 最小值在右边 left=mid+1
mid值小 → 最小值在左边 right=mid
一句话总结:找最小只看右,大右小左。
public int findMin(int[] nums) {
int left=0;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]>nums[right]){
left=mid+1;
}else{
right=mid;
}
}
return nums[left];
}
变式四:二分答案(最值二分、最难必考)
经典题:LC875 爱吃香蕉的珂珂
题目极简说明:给定每堆香蕉数量、小时数h,求最慢但能吃完的最小速度k。
题型特征(区别前面所有):
- 不找数组下标,二分的是「答案数值」
- 求:满足条件的最小值 / 最大值
万能模板四步:
- 划定答案取值范围:left = 下界,right = 上界
- 实现 check (mid):判断当前 mid 数值是否满足题目要求
- mid 可行:记录答案,缩小范围找更小值
right = mid - 1 - mid 不可行:增大取值
left = mid + 1
示例逻辑
// check:速度k是否能在h小时吃完所有香蕉
boolean check(int[] piles, int k, int h) {
int hour = 0;
for (int p : piles) {
hour += p / k;
if (p % k != 0) hour++;
}
return hour <= h;
}
完整模板
public int minEatingSpeed(int[] piles, int h) {
int left=1;
int right=0;
for(int num:piles){
right=Math.max(right,num);
}
while(left<=right){
int mid=left+(right-left)/2;
long time=0;
for(int p:piles){
time+=(p+mid-1)/mid;
}
if(time<=h){
right=mid-1;
}else{
left=mid+1;
}
}
return left;
}
一句话总结:二分答案不看数组有序无序,只看合不合法,找最优最值。
终极4类二分速区分(做题秒判断)
1. 普通有序无重复 → 基础二分(LC35)
2. 有序有重复、找区间边界 → 边界二分(LC34)
3. 数组旋转、局部有序 → 旋转二分(LC33/153)
4. 求最小/最大合法值、不找下标 → 二分答案(LC875)
终极四大题型对照表(考试直接秒选)
| 题型 | 代表题 | 核心操作 | 最大特点 |
|---|---|---|---|
| 基础二分 | 35 | 相等直接返回 | 纯有序、找位置 |
| 边界二分 | 34 | 相等不返回,压缩边界 | 有重复、找首尾 |
| 旋转数组二分 | 33、153 | 先判有序段再搜索 | 数组局部有序 |
| 二分答案 | 875 | check 校验可行性 | 求最值、不找下标 |
二分所有坑 一次性总结
- 普通二分:相等 return
- 边界二分:相等 不 return
- 旋转数组:不能直接二分,必须先判哪边有序
- 二分答案:答案不是下标,是mid本身
- 永远用
left + (right-left)/2防溢出