第 06 站 · 线性结构

二分查找与答案二分

左闭右开区间找「第一个为真」 O(log n) 次判定

周赛难度分难度分 1182–难度分 1946· 中位难度分 1746（14/29 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 06 站 · 29 题

先学: 原地数组
学完去: 二叉搜索树
分段调度
面试频次: 7 家公司考过 · 面经出现 10 次TikTok / ByteDance 3、Rippling 2、Amazon 1、DoorDash 1、Goldman Sachs 1

先做这道

LC 35搜索插入位置简单

卡住再看

实现第一个不小于目标的位置，统一命中与插入两种情况。

要点

先把问题改写成单调的判定 ok(x)：前面全是假、后面全是真，然后二分找第一个真。
区间 [lo, hi) 左闭右开：ok(mid) 时 hi = mid，否则 lo = mid + 1；循环条件 lo < hi，结束时 lo 就是答案。
答案范围已知、给定一个答案能 O(n) 验证时，直接对答案二分：最小速度、最大化最小值都是这一类。

易错点

lo = mid 配合向下取整的 mid 会死循环；用这个模板时只写 lo = mid + 1。
(lo + hi) / 2 在 C++、Java、Go 里可能溢出，写成 lo + (hi - lo) / 2。
hi 本身不会被检查：上界要取到一定可行的值，否则返回的 hi 会被误当成答案。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

二分查找 · 每次排除一半

在有序数组中查找 23

换个输入

123

164

235

386

567

当前处理已发现 / 已计算答案

目标: 23
left: 0
right: 7
mid: —

初始搜索区间包含整个有序数组。下方数字是数组下标。

速度

步骤 1 / 5

始终成立如果目标存在，它始终位于闭区间 [left, right] 内。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 35。

Python

from typing import Callable


def first_true(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    """Smallest x in [lo, hi) with ok(x), where ok goes False..False True..True; hi if none."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid  # mid may be the answer: keep it in range
        else:
            lo = mid + 1
    return lo


def lower_bound(nums: list[int], target: int) -> int:
    """First index whose value is >= target (len(nums) if none)."""
    return first_true(0, len(nums), lambda i: nums[i] >= target)

C++

// Smallest x in [lo, hi) with ok(x), where ok goes false..false true..true; hi if none.
long long firstTrue(long long lo, long long hi, const function<bool(long long)>& ok) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;  // mid may be the answer: keep it in range
        else lo = mid + 1;
    }
    return lo;
}

// First index whose value is >= target (nums.size() if none).
int lowerBound(const vector<int>& nums, int target) {
    return firstTrue(0, nums.size(), [&](long long i) { return nums[i] >= target; });
}

Java

import java.util.function.LongPredicate;

class Solution {
    // Smallest x in [lo, hi) with ok(x), where ok goes false..false true..true; hi if none.
    long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) hi = mid; // mid may be the answer: keep it in range
            else lo = mid + 1;
        }
        return lo;
    }

    // First index whose value is >= target (nums.length if none).
    int lowerBound(int[] nums, int target) {
        return (int) firstTrue(0, nums.length, i -> nums[(int) i] >= target);
    }
}

// firstTrue returns the smallest x in [lo, hi) with ok(x), where ok goes
// false..false true..true; hi if none. sort.Search is the same idea.
func firstTrue(lo, hi int, ok func(int) bool) int {
	for lo < hi {
		mid := lo + (hi-lo)/2
		if ok(mid) {
			hi = mid // mid may be the answer: keep it in range
		} else {
			lo = mid + 1
		}
	}
	return lo
}

// lowerBound returns the first index whose value is >= target (len(nums) if none).
func lowerBound(nums []int, target int) int {
	return firstTrue(0, len(nums), func(i int) bool { return nums[i] >= target })
}

常见变体

这一站的题还会用到下面 3 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

二分答案：在答案区间上找第一个可行值时间 O(n log M)，M 是答案范围 · 空间 O(1)

题目要「最小的可行速度 / 容量 / 天数」，而且可行性随答案单调（速度越快越吃得完）：直接在答案的取值范围上二分，每次用一个 O(n) 的检查函数判断 mid 行不行。LC 875 爱吃香蕉的珂珂、LC 1011、LC 410 都是这个形状。

Python

def min_speed(piles: list[int], hours: int) -> int:
    """Smallest eating speed that finishes every pile within hours (LC 875)."""

    def ok(speed: int) -> bool:  # monotone: a faster speed never needs more hours
        return sum((p - 1) // speed + 1 for p in piles) <= hours

    lo, hi = 1, max(piles)  # the answer is in [lo, hi]; hi always works
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid  # mid works: the answer is mid or smaller
        else:
            lo = mid + 1
    return lo

C++

// Smallest eating speed that finishes every pile within hours (LC 875).
int minSpeed(const vector<int>& piles, long long hours) {
    auto ok = [&](int speed) {  // monotone: a faster speed never needs more hours
        long long need = 0;
        for (int p : piles) need += (p - 1) / speed + 1;
        return need <= hours;
    };
    int lo = 1, hi = *max_element(piles.begin(), piles.end());  // the answer is in [lo, hi]
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;  // mid works: the answer is mid or smaller
        else lo = mid + 1;
    }
    return lo;
}

Java

class Solution {
    // Smallest eating speed that finishes every pile within hours (LC 875).
    int minSpeed(int[] piles, long hours) {
        int lo = 1, hi = Arrays.stream(piles).max().getAsInt(); // the answer is in [lo, hi]
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (ok(piles, hours, mid)) hi = mid; // mid works: the answer is mid or smaller
            else lo = mid + 1;
        }
        return lo;
    }

    // Monotone: a faster speed never needs more hours.
    private boolean ok(int[] piles, long hours, int speed) {
        long need = 0;
        for (int p : piles) need += (p - 1) / speed + 1;
        return need <= hours;
    }
}

import "slices"

// minSpeed returns the smallest eating speed that finishes every pile within hours (LC 875).
func minSpeed(piles []int, hours int) int {
	ok := func(speed int) bool { // monotone: a faster speed never needs more hours
		need := 0
		for _, p := range piles {
			need += (p-1)/speed + 1
		}
		return need <= hours
	}
	lo, hi := 1, slices.Max(piles) // the answer is in [lo, hi]
	for lo < hi {
		mid := lo + (hi-lo)/2
		if ok(mid) {
			hi = mid // mid works: the answer is mid or smaller
		} else {
			lo = mid + 1
		}
	}
	return lo
}

旋转数组：先判断哪一半有序时间 O(log n) · 空间 O(1)

有序数组被旋转过一次（LC 33、LC 153），整体不再单调，但 mid 两边至少有一半有序：先看 nums[lo] <= nums[mid] 判断左半有序，再看 target 落不落在有序那一半里。用闭区间 [lo, hi]，找到就返回。

Python

def search_rotated(nums: list[int], target: int) -> int:
    """Index of target in a rotated sorted array of distinct values, or -1 (LC 33)."""
    lo, hi = 0, len(nums) - 1  # closed range [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:  # the left half [lo, mid] is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # the right half [mid, hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

C++

// Index of target in a rotated sorted array of distinct values, or -1 (LC 33).
int searchRotated(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;  // closed range [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {  // the left half [lo, mid] is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {  // the right half [mid, hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Java

class Solution {
    // Index of target in a rotated sorted array of distinct values, or -1 (LC 33).
    int searchRotated(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1; // closed range [lo, hi]
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) { // the left half [lo, mid] is sorted
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else { // the right half [mid, hi] is sorted
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

// searchRotated returns the index of target in a rotated sorted array of distinct values, or -1.
func searchRotated(nums []int, target int) int {
	lo, hi := 0, len(nums)-1 // closed range [lo, hi]
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if nums[mid] == target {
			return mid
		}
		if nums[lo] <= nums[mid] { // the left half [lo, mid] is sorted
			if nums[lo] <= target && target < nums[mid] {
				hi = mid - 1
			} else {
				lo = mid + 1
			}
		} else { // the right half [mid, hi] is sorted
			if nums[mid] < target && target <= nums[hi] {
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
	}
	return -1
}

找峰值：和右邻居比坡度时间 O(log n) · 空间 O(1)

数组没有整体有序，但相邻元素不相等时，往上坡走一定能走到峰：nums[mid] < nums[mid + 1] 说明右边有峰，否则 mid 或它左边有峰。LC 162 寻找峰值、LC 852 山脉数组的峰顶都用这一比较。

Python

def find_peak(nums: list[int]) -> int:
    """Index of an element larger than its neighbours (LC 162); adjacent values differ."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:  # uphill to the right: a peak lies in (mid, hi]
            lo = mid + 1
        else:  # downhill: mid or something left of it is a peak
            hi = mid
    return lo

C++

// Index of an element larger than its neighbours (LC 162); adjacent values differ.
int findPeak(const vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;  // uphill to the right: a peak lies in (mid, hi]
        else hi = mid;  // downhill: mid or something left of it is a peak
    }
    return lo;
}

Java

class Solution {
    // Index of an element larger than its neighbours (LC 162); adjacent values differ.
    int findPeak(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[mid + 1]) lo = mid + 1; // uphill to the right: a peak lies in (mid, hi]
            else hi = mid; // downhill: mid or something left of it is a peak
        }
        return lo;
    }
}

// findPeak returns the index of an element larger than its neighbours; adjacent values differ.
func findPeak(nums []int) int {
	lo, hi := 0, len(nums)-1
	for lo < hi {
		mid := lo + (hi-lo)/2
		if nums[mid] < nums[mid+1] { // uphill to the right: a peak lies in (mid, hi]
			lo = mid + 1
		} else { // downhill: mid or something left of it is a peak
			hi = mid
		}
	}
	return lo
}

为什么对

不变式：lo 左边全是 false，hi 及其右边全是 true（或越界）。ok(mid) 为真就 hi = mid，否则 lo = mid + 1，两种更新都保持不变式。前提是 ok 单调：前一段全 false、后一段全 true。
终止性：lo < hi 时 mid = lo + (hi − lo) / 2 满足 lo ≤ mid < hi，每轮区间严格缩小；结束时 lo == hi，按不变式它就是第一个 true。
二分答案成立也是因为单调：速度越快越能按时完成，上限越大越容易满足，可行性检查对答案单调，就能对答案本身二分。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

我先把问题改写成一个单调的判定 ok(x)：前面一段全是 false，后面全是 true，然后找第一个 true。在半开区间 [lo, hi) 上，ok(mid) 为真就 hi = mid，否则 lo = mid + 1，始终保持 lo 左边都是 false、hi 往右都是 true。每轮区间严格变小，结束时 lo 等于 hi，就是答案。判定是 O(n) 的话，总复杂度是 O(n log 范围)。

English

I first rewrite the problem as a monotone check ok(x) that is false and then true, and search for the first true. On the half-open range from lo to hi, I set hi to mid when ok(mid) holds and lo to mid plus one otherwise, which keeps everything left of lo false and everything from hi on true. The range shrinks every round, and when lo meets hi that index is the answer. With an O(n) check the total cost is O(n log of the range).

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

不变式：lo 左边全是 false，hi 及其右边全是 true（或越界）。ok(mid) 为真就 hi = mid，否则 lo = mid + 1，两种更新都保持不变式。前提是 ok 单调：前一段全 false、后一段全 true。
终止性：lo < hi 时 mid = lo + (hi − lo) / 2 满足 lo ≤ mid < hi，每轮区间严格缩小；结束时 lo == hi，按不变式它就是第一个 true。
二分答案成立也是因为单调：速度越快越能按时完成，上限越大越容易满足，可行性检查对答案单调，就能对答案本身二分。

小测

5 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

5 道题

lo, hi = 0, len(a)；while lo < hi：mid = (lo + hi) // 2；若 a[mid] < x 则 lo = mid + 1，否则 hi = mid。对有序数组 a，循环结束时 lo 是什么？
- 第一个满足 a[i] >= x 的下标；没有这样的元素时是 len(a)
- 某个满足 a[i] == x 的下标，找不到时是 -1
- 第一个满足 a[i] > x 的下标
- 最后一个满足 a[i] < x 的下标
「二分答案」（在答案的取值范围上二分，每次用 check(mid) 判断可行）需要满足什么条件？
- 输入数组已排序
- 输入里没有重复元素
- 答案一定是整数
- check 在取值范围上单调：某个值可行，比它大的值也都可行（或反过来）
在 Java 或 C++ 里，为什么常写 mid = lo + (hi - lo) / 2，而不是 mid = (lo + hi) / 2？
- 前者更快，少一次除法
- lo + hi 可能超出 int 范围而溢出，hi - lo 不会
- 前者向上取整，后者向下取整
- 只有前者在 lo 为负数时正确

初始 hi - lo = n，每次调用 ok 需要 O(m)。时间复杂度是？

def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

O(m + log n)
O(m log n)
O(log n)
O(n·m)

a 是有序列表。最坏情况下的时间复杂度是？（n = len(a)）

def contains(a, x):
    if not a:
        return False
    mid = len(a) // 2
    if a[mid] == x:
        return True
    if a[mid] < x:
        return contains(a[mid + 1:], x)
    return contains(a[:mid], x)

O(n log n)
O(log n)
O(n)
O(log² n)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

from typing import Callable

分档练习

本站在 500 路里的 29 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 2

#	题目	一句话思路	难度分
35	搜索插入位置	实现第一个不小于目标的位置，统一命中与插入两种情况。
852	山脉数组的峰顶索引	在山脉数组上二分上升与下降的分界，控制中点邻居访问。	难度分 1182

核心 19

#	题目	一句话思路	难度分
34	在排序数组中查找元素的第一个和最后一个位置	分别查找左右边界，避免重复值导致任意命中后线性扩展。
33	搜索旋转排序数组	根据哪一半有序判断目标所在区间，维持旋转数组搜索不变量。
153	寻找旋转排序数组中的最小值	通过中点与右端比较定位旋转最小值，保留可能成为答案的中点。
162	寻找峰值	通过局部坡度选择仍保证存在峰值的一侧。
74	搜索二维矩阵	把矩阵展平为隐式有序数组，转换线性下标与行列下标。
240	搜索二维矩阵 II	利用行列双向有序性逐行二分，并与右上角线性排除方案比较。
275	H 指数 II	识别引用数与剩余论文数之间的单调条件，找到h指数边界。
540	有序数组中的单一元素	利用单独元素前后成对下标的奇偶变化，定位唯一值。
2300	咒语和药水的成功对数	排序一个数组后对每个阈值查找可配对后缀，避免乘法溢出。	难度分 1477
875	爱吃香蕉的珂珂	把速度转化为向上取整的耗时和，寻找最小可行速度。	难度分 1766
1011	在 D 天内送达包裹的能力	给定载重后顺序模拟所需天数，对最小容量进行二分。	难度分 1725
1482	制作 m 束花所需的最少天数	给定日期统计连续可用花段，二分最早可完成日期。	难度分 1946
1283	使结果不超过阈值的最小除数	将除数增大与向上取整和减小建立单调关系。	难度分 1542
1760	袋子里最少数目的球	把最大袋大小转为所需拆分次数，注意整除时少一次操作。	难度分 1940
2187	完成旅途的最少时间	把时间上界转换为各车完成趟数总和，防止累加溢出。	难度分 1641
2226	每个小孩最多能分到多少糖果	按每人份额计算可分配人数，寻找最大的可行整数份额。	难度分 1646
1898	可移除字符的最大数目	用删除顺序标记和子序列检查组成单调判定函数。	难度分 1913
1552	两球之间的磁力	排序位置后贪心放置球，二分最大的最小间距。	难度分 1920
1870	准时到达的列车最小时速	分开前几段向上取整与末段真实耗时，控制浮点边界。	难度分 1676

进阶 8

#	题目	一句话思路	难度分
81	搜索旋转排序数组 II	处理重复值造成的有序性歧义，并说明最坏复杂度退化。
154	寻找旋转排序数组中的最小值 II	在重复值相等时谨慎缩边，区分可证明的排除与模糊区间。
410	分割数组的最大值	通过贪心计数判定最大分组和上限，二分最小可行答案。
1802	有界数组中指定下标处的最大值	用受相邻差约束的最小两侧总和，判定给定峰值是否可行。	难度分 1929
378	有序矩阵中第 K 小的元素	按值域二分并计算矩阵中不超过中值的元素数量。
719	找出第 K 小的数对距离	排序后以双指针统计距离不超过阈值的数对，再按距离二分。
1095	山脉数组中查找目标值	先定位峰顶再在两侧分别二分，缓存访问以控制接口调用次数。	难度分 1827
4	寻找两个正序数组的中位数	在较短数组上二分切分点，利用两侧边界条件求联合中位数。

本站 OA 真题 118

Build Blocks and Obstacles on a Number LineMeta
Find Peak ElementMeta
Kth Missing Positive Number (for E4 :)Meta
Get Smaller ItemsAmazon
Get Computational EquivalentsAmazon
Find Minimum MaximumAmazon
Domino Removal ProblemAmazon
Get Max Matching (Match the Column)Amazon
Get Min Time (Earliest Time Usage ≥ Max)Amazon
Count Bought Items (Recurring Shop Purchase)Amazon

全部 118 道

Core Skills

不调库，亲手实现这一站用到的数据结构或算法，四种语言都能判题。

二分查找：lower_bound 与 upper_bound简单