← 返回学习路线

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;
}

二分只有两种思维:

  1. 找数:相等直接返回
  2. 找边界/找答案:相等不返回,继续缩区间

核心区分标准:

  1. 找到目标直接返回:基础精确查找
  2. 找到目标不返回,收缩区间:查找左右边界
  3. 数组分段有序:旋转数组二分
  4. 不在数组找元素,求最值解:二分答案

变式一:基础二分(精确查找 / 插入位置)

经典题: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]),无重复,找目标值下标。

题型特征:整体无序、左右必有一段有序。

核心思路固定套路:

  1. 先看左边是否有序(nums[left] <= nums[mid])
  2. 看 target 在不在有序区间内 → 在就搜有序侧,不在就搜另一侧

1 nums[left] <= nums[mid] → 左区间有序

  • target 落在 [nums[left], nums[mid]]:右边界左移 right=mid-1
  • 否则去右区间查找 left=mid+1
  1. 右区间有序

    • target 落在 [nums[mid], nums[right]]:左边界右移 left=mid+1
    • 否则去左区间查找 right=mid-1
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。

题型特征(区别前面所有):

  1. 不找数组下标,二分的是「答案数值」
  2. 求:满足条件的最小值 / 最大值

万能模板四步:

  1. 划定答案取值范围:left = 下界,right = 上界
  2. 实现 check (mid):判断当前 mid 数值是否满足题目要求
  3. mid 可行:记录答案,缩小范围找更小值 right = mid - 1
  4. 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 防溢出