二分查找简单思路

．548

214人浏览 · 2026-04-28 15:47:40

．548 · 2026-04-28 15:47:40 发布

1. 二分查找是什么？

二分查找是一种在 有序序列 中快速查找目标值的算法。
核心思路：每次拿中间元素与目标值比较，如果不等就排除一半的搜索范围，不断缩小查找区间，直到找到目标或区间为空。

适用条件

数据必须存储在数组中（支持随机访问）
数据必须是有序的（或者虽然无序，但我们通过二分去猜答案，此时“有序”体现在答案的单调性上）

PDF 里给出了一个关键区分：

正常二分：数组有序，直接查找某个元素
猜答案二分：数据本身无序，但我们查找的是可能的答案值（例如最大容量、最小天数等），答案值的候选空间是单调的，可以用二分缩小范围

2. 二分查找的三种常用模板

PDF第6页总结了三种代码框架，核心区别在于循环条件和边界更新方式。

模板一：`start + 1 < end`

int start = 0, end = len - 1;
while (start + 1 < end) {
    int mid = start + (end - start) / 2;
    if (nums[mid] < target)
        start = mid;       // 不跳过mid，保留可能答案
    else
        end = mid;
}
// 最后剩下两个候选，再分别判断 start 和 end

特点：循环结束时剩余两个元素，必须额外判断。适合查找最后一个小于target的位置这类需要“保留”的场景。

模板二：`start < end`（左闭右开）

int start = 0, end = len;   // 注意：右边界不可达
while (start < end) {
    int mid = start + (end - start) / 2;
    if (nums[mid] < target)
        start = mid + 1;
    else
        end = mid;
}
// 最后 start == end，返回值可能是 start 或需再判断

特点：常用于找第一个大于等于target的位置，右边界是开区间。

模板三：`start <= end`（左闭右闭，最通用的标准模板）

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)
        right = mid - 1;
    else
        left = mid + 1;
}
return -1;

特点：区间内所有元素都会被检查，找到时立即返回。适用于精确查找，也是面试中最常用的板子。

我自己面试时首选模板三，因为它最直接、边界不会出现漏判。遇到“猜答案”类题目时，通常也是用模板三的骨架，只是在判断mid时改为调用一个valid()函数。

3. 题型一：正常二分 —— Search Insert Position (35, Easy)

题目：给定一个有序数组和一个目标值，如果目标值存在则返回索引，否则返回它将被插入的位置。

分析：就是标准的二分查找，找不到时返回left（为什么？因为left最终会指向第一个大于target的位置）。

模板三直接套用：

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)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;  // 此时 left 正好是插入位置
}

4. 题型二：猜答案二分 —— Capacity To Ship Packages (1011, Medium)

题目大意：给定货物重量数组weights，必须按顺序运输，要求在days天内运完，每天最少运一趟，问每天运输的最小容量应该是多少？

关键思路：答案是容量，它有一个明确的单调性：

如果容量 C 不够（即需要的天数 > days），那么任何小于 C 的容量一定也不够。
如果容量 C 足够（需要的天数 ≤ days），那么我们可以尝试缩小容量看看还有没有更小的。

于是我们可以二分答案，下界 low = max(weights) （至少能装下最重的包裹），上界 high = sum(weights) （一天全运走）。

核心代码（PDF第8页的模板）：

public int splitArray(int[] nums, int m) {  // 和本题几乎一样，只是m就是days
    int sum = Arrays.stream(nums).sum();
    int max = Arrays.stream(nums).max().getAsInt();
    return binary(nums, m, sum, max);
}

private int binary(int[] nums, int m, int high, int low) {
    int mid = 0;
    while (low <= high) {          // 模板三骨架
        mid = low + (high - low) / 2;
        if (valid(nums, m, mid))   // 容量 mid 可行吗？
            high = mid - 1;        // 可行，尝试更小的容量
        else
            low = mid + 1;         // 不可行，必须增大容量
    }
    return low; // 循环结束时 low 就是满足条件的最小容量
}

// 判定函数：给定容量 subArraySum，需要多少天？
private boolean valid(int[] nums, int m, int subArraySum) {
    int curSum = 0, count = 1;
    for (int num : nums) {
        curSum += num;
        if (curSum > subArraySum) {
            curSum = num;   // 从当前货物重新开始累加
            count++;
            if (count > m) return false;
        }
    }
    return true;
}

对Capacity To Ship Packages的改写（几乎一样，把m换成days即可）：

public int shipWithinDays(int[] weights, int days) {
    int max = 0, sum = 0;
    for (int w : weights) {
        max = Math.max(max, w);
        sum += w;
    }
    int left = max, right = sum;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canShip(weights, days, mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean canShip(int[] weights, int days, int capacity) {
    int curSum = 0, needDays = 1;
    for (int w : weights) {
        curSum += w;
        if (curSum > capacity) {
            needDays++;
            curSum = w;
            if (needDays > days) return false;
        }
    }
    return true;
}

这类猜答案二分在PDF里还列出了同类型的题：

1. Magnetic Force Between Two Balls
1. Minimum Number of Days to Make m Bouquets
1. Find the Smallest Divisor Given a Threshold
  它们都有一样的模式：答案值在一个区间内单调，套用“二分答案 + 判定函数”即可。

5. 题型三：二分优化LIS —— Longest Increasing Subsequence (300, Medium)

题目：求最长严格递增子序列的长度（子序列不要求连续）。
传统DP：dp[i] 表示以 nums[i] 结尾的LIS长度，O(n²)。

二分优化：维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。
这样 tails 数组一定是严格递增的，我们可以用二分查找来更新它，时间复杂度 O(n log n)。

过程：

遍历 nums，对于每个数 x：
1. 在 tails 中找到第一个 ≥ x 的位置（用 lower_bound）
2. 如果找不到（即 x 比所有 tails 元素都大），就把 x 追加到 tails 末尾
3. 否则，用 x 替换那个位置的值（因为找到了更小的末尾，有利于后序扩展）

代码：

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = 0, j = size;
        // 二分查找第一个 >= x 的位置
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (tails[mid] < x)
                i = mid + 1;
            else
                j = mid;
        }
        tails[i] = x;
        if (i == size) size++; // 如果插在末尾，长度增加
    }
    return size;
}

这里二分用的是模板二（左闭右开），因为我们要找的是插入位置。

6. 总结 Binary Search 要点

题型	模板选择	关键点
直接查找	模板三 `while(l<=r)`	最好记，适用绝大多数场景
猜答案	模板三骨架 + `valid()` 函数	确定答案的上下界，答案单调性是核心
LIS优化	模板二 `while(l<r)` 找下界	维护单调递增的 `tails` 数组