数据结构与算法-二分查找

2020-10-21 HGNULB 约 48 分钟

文章信息 2 个分类 2 个标签

分类

常见二分查找模板与分类

二分查找的思想极其简单：每轮利用单调性排除一半搜索空间。但它也是「思路五分钟、写对一小时」的典型，面试中翻车基本集中在四个细节上，动笔前先在心里过一遍。

[!red]

区间开闭：先定义清楚搜索区间是闭区间 [left, right] 还是左闭右开 [left, right)，初始化、循环条件、收缩方式三者必须与之匹配，全程不许换定义。本文统一使用闭区间 [left, right]。

循环条件：闭区间对应 while (left <= right)，因为 left > right 时区间才为空；若收缩时需要保留 mid 作为候选（如求最小值、峰值），改用 while (left < right)，结束时 left == right 即答案。两者混用会漏查元素或死循环。

mid 取整与防溢出：统一写 mid = left + (right - left) / 2，既是下取整，又避免 left + right 相加溢出。若收缩逻辑中出现 left = mid（不加一），必须改上取整 mid = left + (right - left + 1) / 2，否则区间只剩两个元素时 mid 永远等于 left，死循环。

边界收缩：能确定 mid 不是答案时，用 left = mid + 1 / right = mid - 1 把它彻底排除；mid 仍可能是答案时，用 right = mid 保留它（配合 left < right）。每轮必须让区间严格变小，这是不死循环的根本保证。

判断一道题能不能二分，关键不是「数组是否有序」，而是能否构造一个单调的判定函数：搜索空间里存在一条分界线，左边全是「不满足」，右边全是「满足」（或反之）。数组有序只是单调性最直观的来源，值域二分、答案二分同样成立。

模板一：标准二分查找

[!blue]
精确查找等于目标值的元素：闭区间 [left, right]，循环条件 left <= right，三分支分别处理命中、偏小、偏大。命中直接返回下标，区间为空返回 -1。

循环不变量：如果 target 存在，它一定落在 [left, right] 内。命中时可以立即返回，是因为题目只要求任意一个匹配位置；nums[mid] != target 时 mid 已被验证不是答案，用 mid ± 1 彻底排除它，区间每轮至少缩小一格，不会死循环。时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

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

left, right := 0, len(nums)-1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
        return mid
    } else if nums[mid] < target {
        left = mid + 1
    } else {
        right = mid - 1
    }
}
return -1

704. 二分查找

核心观察：数组升序且元素互不相同，target 与 nums[mid] 的大小关系直接告诉我们答案在哪一半。做法就是标准模板的逐字实现：命中返回下标，偏小去右半，偏大去左半，区间为空返回 -1。这道题是所有二分题的「地基」，面试里如果这题写不干净，后面的变体题基本没有机会。

class Solution {
    public int search(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 -1;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

时间复杂度：$O(\log n)$，每轮排除一半区间。

空间复杂度：$O(1)$。

367. 有效的完全平方数

核心观察：mid * mid 随 mid 单调递增，所以「是否存在整数平方等于 num」可以在整数域上二分。做法：num == 1 单独处理后，在 [1, num / 2] 上找满足 mid * mid == num 的数——num >= 2 时平方根不会超过 num / 2。用乘法比较代替开方，避免浮点误差；Java 中 mid * mid 可能超出 int，要用 long 承接。

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }
        int left = 1, right = num / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long square = (long) mid * mid; // 防止 int 乘法溢出
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    left, right := 1, num/2
    for left <= right {
        mid := left + (right-left)/2
        if mid*mid == num {
            return true
        } else if mid*mid < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

时间复杂度：$O(\log num)$。

空间复杂度：$O(1)$。

模板二：二分查找下界问题

[!blue]
查找左边界：第一个大于等于（或第一个等于）目标值的元素。与模板一的核心区别是：命中时不能直接返回——当前 mid 只是「一个」满足条件的位置，左边可能还有更靠前的，所以先记录 res = mid，再 right = mid - 1 继续向左逼近。

循环不变量：res 始终是目前已知的最靠左的满足条件的位置，[left, right] 内可能还有更靠左的。也可以不记 res：闭区间二分结束时 left 恰好停在第一个满足 >= target 的位置（left == n 表示不存在），这个性质本身值得记住。时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

int left = 0, right = nums.length - 1;
int res = -1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
        res = mid;           // mid 满足条件，记下后继续向左找更靠前的
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return res;

left, right := 0, len(nums)-1
res := -1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] >= target {
        res = mid // mid 满足条件，记下后继续向左找更靠前的
        right = mid - 1
    } else {
        left = mid + 1
    }
}
return res

34. 在排序数组中查找元素的第一个和最后一个位置

核心观察：第一个位置就是左边界，最后一个位置就是右边界，各做一次二分即可。两次二分唯一的区别在 nums[mid] == target 分支：找左边界时记录答案并 right = mid - 1 继续向左压；找右边界时记录答案并 left = mid + 1 继续向右压。面试中这题是「会不会边界二分」的试金石，千万不要写成找到一个位置后向两边线性扩展——重复元素多时会退化成 $O(n)$。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeft(nums, target), findRight(nums, target)};
    }

    // 找第一个等于 target 的位置
    private int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                res = mid;
                right = mid - 1;
            }
        }
        return res;
    }

    // 找最后一个等于 target 的位置
    private int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                res = mid;
                left = mid + 1;
            }
        }
        return res;
    }
}

func searchRange(nums []int, target int) []int {
    return []int{findLeft(nums, target), findRight(nums, target)}
}

// 找第一个等于 target 的位置
func findLeft(nums []int, target int) int {
    left, right := 0, len(nums)-1
    res := -1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            res = mid
            right = mid - 1
        }
    }
    return res
}

// 找最后一个等于 target 的位置
func findRight(nums []int, target int) int {
    left, right := 0, len(nums)-1
    res := -1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            res = mid
            left = mid + 1
        }
    }
    return res
}

时间复杂度：$O(\log n)$，两次独立二分。

空间复杂度：$O(1)$。

35. 搜索插入位置

核心观察：插入位置的定义恰好是「第一个大于等于 target 的下标」，本质就是下界问题。做法：用闭区间标准写法二分，命中直接返回；未命中时循环结束，left 恰好停在第一个大于 target 的位置（所有元素都小于 target 时 left == n），直接返回 left。理解「结束时 left 停在哪」比背代码重要得多。

class Solution {
    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 即第一个大于 target 的位置
    }
}

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        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 即第一个大于 target 的位置
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

278. 第一个错误的版本

核心观察：版本序列形如「好好好…坏坏坏」，是一个天然的单调布尔序列，找第一个坏版本就是在布尔序列上找左边界。做法：isBadVersion(mid) 为 true 时 mid 是候选，记录后 right = mid - 1 继续向左；为 false 时坏版本一定在右边，left = mid + 1。题目保证存在坏版本，所以 res 必被赋值。这题的价值在于让你意识到：二分的对象不一定是数组，任何单调判定函数都可以。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                res = mid; // mid 是坏版本，继续向左找更早的
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}

func firstBadVersion(n int) int {
    left, right := 1, n
    res := -1
    for left <= right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            res = mid // mid 是坏版本，继续向左找更早的
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return res
}

时间复杂度：$O(\log n)$，调用 isBadVersion 的次数为对数级。

空间复杂度：$O(1)$。

744. 寻找比目标字母大的最小字母

核心观察：要找的是第一个严格大于 target 的字母，即上确界（upper bound），与「大于等于」的下界只差一个等号：letters[mid] <= target 时 mid 不合格，必须 left = mid + 1。做法：二分结束后 left 指向第一个大于 target 的位置；若 left 越界，说明所有字母都不大于 target，按题意循环回 letters[0]。面试中被问到 lower bound 与 upper bound 的区别，答案就浓缩在这一个等号里。

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1; // 等于 target 也不合格，向右找严格更大的
            } else {
                right = mid - 1;
            }
        }
        return left == letters.length ? letters[0] : letters[left];
    }
}

func nextGreatestLetter(letters []byte, target byte) byte {
    left, right := 0, len(letters)-1
    for left <= right {
        mid := left + (right-left)/2
        if letters[mid] <= target {
            left = mid + 1 // 等于 target 也不合格，向右找严格更大的
        } else {
            right = mid - 1
        }
    }
    if left == len(letters) {
        return letters[0]
    }
    return letters[left]
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

1060. 有序数组中的缺失元素

核心观察：定义 miss(i) = nums[i] - nums[0] - i，表示 nums[0..i] 之间缺失了多少个数，它随 i 单调不减——单调性一出现，就可以二分。做法：找第一个 miss(i) >= k 的下标 left（标准下界二分），则第 k 个缺失的数落在 nums[left-1] 之后，还差 k - miss(left-1) 个，答案为 nums[left-1] + k - miss(left-1)。若 k 超过数组内缺失总数，循环结束时 left == n，公式同样成立（k >= 1 保证 left >= 1，不会越界）。

class Solution {
    public int missingElement(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (miss(nums, mid) < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[left - 1] + k - miss(nums, left - 1);
    }

    // nums[0..i] 之间缺失的数的个数
    private int miss(int[] nums, int i) {
        return nums[i] - nums[0] - i;
    }
}

func missingElement(nums []int, k int) int {
    // miss(i) 表示 nums[0..i] 之间缺失的数的个数
    miss := func(i int) int {
        return nums[i] - nums[0] - i
    }

    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if miss(mid) < k {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return nums[left-1] + k - miss(left-1)
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

模板三：二分查找上界问题

[!blue]
查找右边界：最后一个小于等于（或最后一个等于）目标值的元素。与下界完全对称：nums[mid] <= target 时 mid 是候选答案，记录 res = mid 后 left = mid + 1 继续向右逼近，看右边还有没有更靠后的。

循环不变量：res 始终是目前已知的最靠右的满足条件的位置。同样有一条免记 res 的性质：闭区间二分结束时 right 是最后一个「偏小」的位置、left 是第一个「偏大」的位置，两者相邻。时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

int left = 0, right = nums.length - 1;
int res = -1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] <= target) {
        res = mid;           // mid 满足条件，记下后继续向右找更靠后的
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return res;

left, right := 0, len(nums)-1
res := -1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] <= target {
        res = mid // mid 满足条件，记下后继续向右找更靠后的
        left = mid + 1
    } else {
        right = mid - 1
    }
}
return res

34. 在排序数组中查找元素的第一个和最后一个位置

该题的 findRight 就是上界模板的直接应用：nums[mid] == target 时记录答案并 left = mid + 1，继续向右找最后一个等于 target 的位置。完整代码见模板二一节，此处不再重复。

69. x 的平方根

[!blue]
求 $\sqrt{x}$ 向下取整，等价于找最大的 mid 满足 mid * mid <= x。

核心观察：「最大的满足条件的数」就是典型上界问题。做法：在 [1, x] 上二分，mid <= x / mid 时 mid 是候选，记录后 left = mid + 1 继续向右找更大的。用除法 x / mid 代替 mid * mid 比较可以直接规避乘法溢出（mid >= 1 保证除法安全），比转 long 更省心。x == 0 单独返回 0。

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int left = 1, right = x;
        int res = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) { // 用除法比较，避免 mid * mid 溢出
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

func mySqrt(x int) int {
    if x == 0 {
        return 0
    }
    left, right := 1, x
    res := 0
    for left <= right {
        mid := left + (right-left)/2
        if mid <= x/mid { // 用除法比较，避免 mid*mid 溢出
            res = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return res
}

时间复杂度：$O(\log x)$。

空间复杂度：$O(1)$。

441. 排列硬币

[!blue]
我们要找最大的 k，使得前 k 行的硬币数之和不超过 n：$1 + 2 + \cdots + k = \frac{k(k+1)}{2} \le n$。

所以题目可以转化为：给定 n，求满足 k(k+1)/2 <= n 的最大整数 k。

核心观察：k(k+1)/2 随 k 单调递增，找「最大的满足者」是上界问题。做法：在 [0, n] 上二分，和恰好等于 n 直接返回；否则循环结束时 right 恰好停在最后一个满足 sum <= n 的 k 上——这正是闭区间二分的结束性质（right 是最后一个「偏小」位置），直接返回 right。Java 中 mid * (mid + 1) 会溢出 int，用 long 计算。

class Solution {
    public int arrangeCoins(int n) {
        long left = 0, right = n;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long sum = mid * (mid + 1) / 2; // long 防止溢出
            if (sum == n) {
                return (int) mid;
            } else if (sum < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (int) right;
    }
}

func arrangeCoins(n int) int {
    left, right := 0, n
    for left <= right {
        mid := left + (right-left)/2
        sum := mid * (mid + 1) / 2
        if sum == n {
            return mid
        } else if sum < n {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right // 结束时 right 是最后一个满足 sum <= n 的 k
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

模板四：旋转排序数组二分查找

[!blue]
有序数组被部分旋转，例如 [0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]。

核心观察：以 mid 为界把数组切成两半，至少有一半是有序的——旋转点只有一个，不可能同时落在两半里。用 nums[left] <= nums[mid] 判断左半是否有序（注意是 <=，处理 left == mid 的退化情况），再看 target 是否落在有序那半的值域范围内：在就收缩到那半，不在就去另一半。每轮仍能排除一半，时间复杂度 $O(\log n)$。

int left = 0, 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 (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;

left, right := 0, len(nums)-1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
        return mid
    }
    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

33. 搜索旋转排序数组

核心观察：元素互不相同，直接套模板四——先判断哪半有序，再判断 target 是否在有序半的值域内。两个易错点值得在面试中主动说出来：判断左半有序必须用 nums[left] <= nums[mid]（区间剩一个元素时 left == mid）；范围判断一侧带等号（nums[left] <= target、target <= nums[right]），另一侧严格小于（target == nums[mid] 已在前面命中返回）。

class Solution {
    public int search(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;
            }
            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;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        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
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

81. 搜索旋转排序数组 II

核心观察：与 33 题的唯一区别是允许重复元素。当 nums[left] == nums[mid] == nums[right] 时（如 [1,1,1,0,1] 查 0），三个采样点相等，无法判断哪半有序，只能 left++、right-- 各收缩一格——丢掉的两个值都等于 nums[mid]，已确认不是 target，收缩是安全的。其余情况仍按模板四处理。因为存在退化收缩，最坏时间复杂度退化为 $O(n)$（全部元素相同时），这也是面试官必追问的点。

class Solution {
    public boolean search(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 true;
            }
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                // 无法判断哪半有序，两端各收缩一格
                left++;
                right--;
            } else 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 false;
    }
}

func search(nums []int, target int) bool {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }
        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            // 无法判断哪半有序，两端各收缩一格
            left++
            right--
        } else 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 false
}

时间复杂度：平均 $O(\log n)$，最坏 $O(n)$（元素全部相同时退化为线性收缩）。

空间复杂度：$O(1)$。

153. 寻找旋转排序数组中的最小值

核心观察：拿 nums[mid] 和 nums[right] 比较——不能和 nums[left] 比，因为 nums[mid] > nums[left] 时无法区分「整体有序」和「旋转点在右半」两种情况，而与 nums[right] 的比较结果是无歧义的。做法：若 nums[mid] > nums[right]，旋转点在右半，最小值在 (mid, right]，left = mid + 1；否则右半有序，最小值在 [left, mid]——mid 本身可能就是答案，所以 right = mid 不减一，循环条件相应改用 left < right，结束时 left == right 即最小值下标。元素互不相同，无需处理相等分支。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid; // mid 可能就是最小值，保留
            }
        }
        return nums[left];
    }
}

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid // mid 可能就是最小值，保留
        }
    }
    return nums[left]
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

154. 寻找旋转排序数组中的最小值 II

核心观察：153 的进阶，允许重复元素。当 nums[mid] == nums[right] 时无法判断最小值在哪一侧（对比 [3,1,3,3,3] 与 [3,3,3,1,3]），但可以安全地 right--：即使被丢掉的 nums[right] 恰好是最小值，nums[mid] 上还留着一个相等的值，答案不会丢。其余两个分支与 153 完全一致。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--; // 无法判断方向，安全地丢掉一个重复值
            }
        }
        return nums[left];
    }
}

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right-- // 无法判断方向，安全地丢掉一个重复值
        }
    }
    return nums[left]
}

时间复杂度：平均 $O(\log n)$，最坏 $O(n)$（元素全部相同时）。

空间复杂度：$O(1)$。

剑指 Offer 11. 旋转数组的最小数字

核心观察：与 154 完全相同——允许重复元素的旋转数组求最小值，nums[mid] == nums[right] 时 right-- 退化收缩，其余按与 nums[right] 的比较收缩。

class Solution {
    public int inventoryManagement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }
}

func inventoryManagement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

时间复杂度：平均 $O(\log n)$，最坏 $O(n)$。

空间复杂度：$O(1)$。

面试题 10.03. 搜索旋转数组

核心观察：在 81 题（旋转 + 重复）的基础上，还要求返回最小下标，相当于旋转数组上的左边界二分。两个关键处理：命中 nums[mid] == target 时不直接返回，记录答案后 right = mid - 1 继续向左压；每轮先检查 nums[left] == target——成立时 left 一定是当前区间内的最小匹配下标，可直接返回。判断有序半改用 nums[mid] 与 nums[right] 比较，nums[mid] == nums[right] 时无法判断方向，right-- 退化收缩。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            if (nums[left] == target) {
                return left; // left 是当前区间内最小的匹配下标
            }
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res = mid;
                right = mid - 1; // 继续向左找更小的下标
            } else if (nums[mid] > nums[right]) {
                // 左半有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < nums[right]) {
                // 右半有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                right--;
            }
        }
        return res;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    res := -1
    for left <= right {
        if nums[left] == target {
            return left // left 是当前区间内最小的匹配下标
        }
        mid := left + (right-left)/2
        if nums[mid] == target {
            res = mid
            right = mid - 1 // 继续向左找更小的下标
        } else if nums[mid] > nums[right] {
            // 左半有序
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else if nums[mid] < nums[right] {
            // 右半有序
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else {
            right--
        }
    }
    return res
}

时间复杂度：平均 $O(\log n)$，最坏 $O(n)$（重复元素退化收缩时）。

空间复杂度：$O(1)$。

模板五：二维矩阵二分查找

[!blue]
二维场景下的二分有两种常见形态：一是矩阵整体有序，可按行展开映射为一维数组，对下标二分；二是矩阵只满足行列分别有序，无法展开，改为对值域二分（猜一个答案，用 $O(n)$ 的计数函数验证单调条件）。两题分别对应这两种形态。

74. 搜索二维矩阵

核心观察：每行升序、且每行第一个数大于上一行最后一个数，所以按行展开就是一个长度为 $m \times n$ 的有序数组。做法：对下标区间 [0, m*n-1] 做标准二分，用 mid / n 取行、mid % n 取列，把一维下标映射回二维，完全不需要真的展开数组。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = matrix[mid / n][mid % n]; // 一维下标映射回行列
            if (val == target) {
                return true;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1
    for left <= right {
        mid := left + (right-left)/2
        val := matrix[mid/n][mid%n] // 一维下标映射回行列
        if val == target {
            return true
        } else if val < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

时间复杂度：$O(\log(mn))$。

空间复杂度：$O(1)$。

378. 有序矩阵中第 K 小的元素

核心观察：矩阵只保证行、列分别升序，不能展开成一维有序数组，于是换思路做值域二分（对答案二分）：设 count(x) 为矩阵中小于等于 x 的元素个数，它随 x 单调不减，答案就是第一个满足 count(x) >= k 的 x。做法：在 [matrix[0][0], matrix[n-1][n-1]] 上二分猜答案 mid；统计 count 时从每行末尾维护指针 j 向左收缩——利用行列均有序，j 跨行单调不增，一次统计只需 $O(n)$。count < k 时 left = mid + 1，否则 right = mid（mid 可能就是答案）。最终 left 是第一个满足 count >= k 的值，可以证明它一定出现在矩阵中——否则把它减小到矩阵中的前驱值，count 不变，与「第一个」矛盾。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (countNoMoreThan(matrix, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // 统计矩阵中 <= x 的元素个数，指针 j 跨行单调左移
    private int countNoMoreThan(int[][] matrix, int x) {
        int n = matrix.length;
        int count = 0;
        int j = n - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && matrix[i][j] > x) {
                j--;
            }
            count += j + 1;
        }
        return count;
    }
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)

    // 统计矩阵中 <= x 的元素个数，指针 j 跨行单调左移
    countNoMoreThan := func(x int) int {
        count, j := 0, n-1
        for i := 0; i < n; i++ {
            for j >= 0 && matrix[i][j] > x {
                j--
            }
            count += j + 1
        }
        return count
    }

    left, right := matrix[0][0], matrix[n-1][n-1]
    for left < right {
        mid := left + (right-left)/2
        if countNoMoreThan(mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

时间复杂度：$O(n \log(\max - \min))$，每轮验证 $O(n)$，二分轮数取决于值域跨度。

空间复杂度：$O(1)$。

模板六：峰值二分

[!blue]
寻找数组中的峰值：比较 nums[mid] 与 nums[mid+1]，判断当前处于上坡还是下坡。若 nums[mid] > nums[mid+1]（下坡），则 [left, mid] 内必有峰值——mid 自己可能就是，所以 right = mid 保留它；否则（上坡），[mid+1, right] 内必有峰值，left = mid + 1。

循环不变量：[left, right] 内始终至少存在一个峰值（沿上坡方向走必然撞到峰或边界）。因为收缩时保留候选，循环条件用 left < right；mid 下取整保证 mid < right，所以 mid + 1 永不越界——这就是这个模板不需要任何边界特判的原因。时间复杂度 $O(\log n)$。

int left = 0, right = nums.length - 1;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > nums[mid + 1]) {
        right = mid;      // 下坡，峰值在左侧（含 mid）
    } else {
        left = mid + 1;   // 上坡，峰值在右侧
    }
}
return left;

left, right := 0, len(nums)-1
for left < right {
    mid := left + (right-left)/2
    if nums[mid] > nums[mid+1] {
        right = mid // 下坡，峰值在左侧（含 mid）
    } else {
        left = mid + 1 // 上坡，峰值在右侧
    }
}
return left

162. 寻找峰值

核心观察：题目规定 nums[-1] = nums[n] = -∞ 且相邻元素不相等，所以沿上坡方向走必能到达某个峰值——数组不可能一路升到正无穷。做法：直接套峰值模板，返回任意一个峰值下标即可。面试中值得主动解释「为什么数组无序也能二分」：二分依赖的不是全局有序，而是每轮都能确定某一半必含答案。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid; // 下坡，峰值在左侧（含 mid）
            } else {
                left = mid + 1; // 上坡，峰值在右侧
            }
        }
        return left;
    }
}

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[mid+1] {
            right = mid // 下坡，峰值在左侧（含 mid）
        } else {
            left = mid + 1 // 上坡，峰值在右侧
        }
    }
    return left
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

852. 山脉数组的峰顶索引

核心观察：山脉数组保证先严格递增后严格递减，峰顶唯一，是峰值模板的最简化场景，直接套用即可，连「返回任意峰值」的讨论都省了。

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func peakIndexInMountainArray(arr []int) int {
    left, right := 0, len(arr)-1
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] > arr[mid+1] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

1095. 山脉数组中查找目标值

核心观察：山脉数组由一段升序和一段降序拼成，每段内部都可以标准二分。做法分三步：先用峰值二分找到山顶下标 peak；再在左侧升序段 [0, peak] 中二分，找到就返回（下标更小，优先）；找不到再去右侧降序段 [peak+1, n-1] 二分。降序段只需把比较方向反过来，用一个 asc 参数统一两段逻辑。三次二分共调用 get $O(\log n)$ 次，满足题目对访问次数的限制——这也是不能线性扫描的原因。

/**
 * interface MountainArray {
 *     public int get(int index);
 *     public int length();
 * }
 */
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();

        // 1. 二分找峰顶下标
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int peak = left;

        // 2. 优先在升序段 [0, peak] 中查找
        int idx = binarySearch(mountainArr, target, 0, peak, true);
        if (idx != -1) {
            return idx;
        }
        // 3. 再在降序段 [peak+1, n-1] 中查找
        return binarySearch(mountainArr, target, peak + 1, n - 1, false);
    }

    // asc 表示该区间是否升序
    private int binarySearch(MountainArray mountainArr, int target, int left, int right, boolean asc) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) {
                return mid;
            }
            if ((asc && val < target) || (!asc && val > target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

func findInMountainArray(target int, mountainArr *MountainArray) int {
    n := mountainArr.length()

    // 1. 二分找峰顶下标
    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        if mountainArr.get(mid) < mountainArr.get(mid+1) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    peak := left

    // 2. 优先在升序段 [0, peak] 中查找
    if idx := binarySearch(mountainArr, target, 0, peak, true); idx != -1 {
        return idx
    }
    // 3. 再在降序段 [peak+1, n-1] 中查找
    return binarySearch(mountainArr, target, peak+1, n-1, false)
}

// asc 表示该区间是否升序
func binarySearch(mountainArr *MountainArray, target, left, right int, asc bool) int {
    for left <= right {
        mid := left + (right-left)/2
        val := mountainArr.get(mid)
        if val == target {
            return mid
        }
        if (asc && val < target) || (!asc && val > target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

时间复杂度：$O(\log n)$，三次二分各调用 get 对数次。

空间复杂度：$O(1)$。

其他经典题

[!blue]

百度面试题-有序数组中绝对值最小的元素

540. 有序数组中的单一元素

百度面试题-有序数组中绝对值最小的元素

核心观察：数组升序时绝对值先减后增（谷形），最小绝对值一定出现在正负分界处。做法：先处理两种平凡情况——全非负时答案是 nums[0]，全非正时答案是 nums[n-1]；否则二分找正负分界：nums[mid] == 0 直接返回 0，nums[mid] < 0 说明分界在右边。闭区间二分结束时 left 指向第一个正数、right（即 left - 1）指向最后一个负数，答案取两者中绝对值较小的一个。

class Solution {
    public int findMinAbs(int[] nums) {
        int n = nums.length;
        if (nums[0] >= 0) {
            return nums[0]; // 全非负，最小绝对值是第一个
        }
        if (nums[n - 1] <= 0) {
            return nums[n - 1]; // 全非正，最小绝对值是最后一个
        }

        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == 0) {
                return 0;
            } else if (nums[mid] < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 结束时 left 指向第一个正数，right 指向最后一个负数
        return -nums[right] < nums[left] ? nums[right] : nums[left];
    }
}

func findMinAbs(nums []int) int {
    n := len(nums)
    if nums[0] >= 0 {
        return nums[0] // 全非负，最小绝对值是第一个
    }
    if nums[n-1] <= 0 {
        return nums[n-1] // 全非正，最小绝对值是最后一个
    }

    left, right := 0, n-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == 0 {
            return 0
        } else if nums[mid] < 0 {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    // 结束时 left 指向第一个正数，right 指向最后一个负数
    if -nums[right] < nums[left] {
        return nums[right]
    }
    return nums[left]
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。

540. 有序数组中的单一元素

核心观察：全员异或能解但是 $O(n)$，不满足题目要求的 $O(\log n)$。二分依据的单调性质是：单一元素左侧的成对元素都从偶数下标开始（下标 2k 与 2k+1 相等），单一元素出现后这个配对规律被整体打破。做法：用 mid ^ 1 取 mid 的配对下标（mid 为偶取 mid+1，为奇取 mid-1）；若 nums[mid] == nums[mid^1]，说明 mid 处配对完好，单一元素在右侧，left = mid + 1；否则单一元素在 [left, mid]，right = mid 保留候选。结束时 left == right 即单一元素下标。

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // mid ^ 1：mid 为偶数时取 mid+1，为奇数时取 mid-1
            if (nums[mid] == nums[mid ^ 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

func singleNonDuplicate(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        // mid^1：mid 为偶数时取 mid+1，为奇数时取 mid-1
        if nums[mid] == nums[mid^1] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

时间复杂度：$O(\log n)$。

空间复杂度：$O(1)$。