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

2020-10-21 HGNULB 约 80 分钟

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

分类

数据结构与算法

标签

二分查找 二分查找经典题

一、精确查找

统一思路：在有序搜索区间中比较中点与目标值，相等即返回；偏小排除左半，偏大排除右半。闭区间使用 left <= right，找不到返回 -1。

通用模板：精确查找

int left = 0;
int 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. 二分查找

在升序数组中比较 nums[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[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
        }
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

367. 有效的完全平方数

对整数平方进行精确查找，乘法使用足够宽的整数类型。 平方随候选整数增大而增大，因此可以比较平方值与目标值，按标准二分排除一半区间。

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1;
        long right = num;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;

            if (square == num) {
                return true;
            }

            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

func isPerfectSquare(num int) bool {
    target := int64(num)
    left, right := int64(1), target

    for left <= right {
        mid := left + (right-left)/2
        square := mid * mid
        if square == target {
            return true
        }
        if square < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

74. 搜索二维矩阵

整体有序的矩阵按一维下标映射后查找。 用 mid / 列数 和 mid % 列数 还原行列位置，不需要真正展开矩阵。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = matrix[mid / n][mid % n];

            if (value == target) {
                return true;
            }

            if (value < 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
        value := matrix[mid/n][mid%n]
        if value == target {
            return true
        }
        if value < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

二、找左边界

统一思路：寻找第一个满足条件的位置。满足条件时记录中点并继续向左，不满足时向右；找第一个 >= target 与第一个 > target 只差判定中的等号。

通用模板：找左边界

下面查找第一个 >= target 的位置，不存在返回 -1。查找插入位置时，可以改为返回循环结束后的 left，其范围是 [0, n]。

int left = 0;
int right = nums.length - 1;
int res = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] >= target) {
        // mid 满足条件，记下后继续向左找更靠前的
        res = 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 {
        // mid 满足条件，记下后继续向左找更靠前的
        res = mid
        right = mid - 1
    } else {
        left = mid + 1
    }
}
return res

35. 搜索插入位置

第一个大于等于目标值的位置。 满足条件时继续向左，不满足时向右；全部元素都小于目标值时，返回数组长度。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

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

278. 第一个错误的版本

第一个坏版本。 版本状态呈现“好版本 → 坏版本”的单调变化；中点为坏版本时保留中点并向左查找，否则排除左半。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        // 区间内始终保留第一个错误版本这个答案。
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

func firstBadVersion(n int) int {
    // 用二分查找第一个满足 isBadVersion 的位置。
    left, right := 1, n

    for left < right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

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

第一个严格大于目标字母的位置。 将左边界判定改为严格大于；如果所有字母都不满足，按题意返回第一个字母。

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0;
        int right = letters.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (letters[mid] <= target) {
                // 等于 target 也不合格，向右找严格更大的
                left = mid + 1;
            } 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 {
            // 等于 target 也不合格，向右找严格更大的
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if left == len(letters) {
        return letters[0]
    }
    return letters[left]
}

2300. 咒语和药水的成功对数

第一个满足乘积阈值的位置。 先对药水排序，再对每个咒语二分定位左边界；右侧药水数量就是成功对数，乘积需避免溢出。

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        // 排序让「是否成功」沿下标单调，二分才有立足点。
        Arrays.sort(potions);
        int m = potions.length;
        int[] ans = new int[spells.length];

        for (int i = 0; i < spells.length; i++) {
            // 左闭右开 [lo, hi)，hi = m 给「一瓶都配不上」留合法落点。
            int lo = 0;
            int hi = m;

            while (lo < hi) {
                int mid = (lo + hi) >>> 1;

                // 乘积可达 1e10，必须先转 long 再乘；用除法会因向下取整放宽阈值。
                if ((long) potions[mid] * spells[i] >= success) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }

            // lo 是第一个成功的下标，它右边（含自身）全部成功。
            ans[i] = m - lo;
        }

        return ans;
    }
}

func successfulPairs(spells []int, potions []int, success int64) []int {
    // 排序让「是否成功」沿下标单调，二分才有立足点。
    sort.Ints(potions)
    m := len(potions)
    ans := make([]int, len(spells))
    for i, v := range spells {
        // 左闭右开 [lo, hi)，hi = m 给「一瓶都配不上」留合法落点。
        lo, hi := 0, m
        for lo < hi {
            mid := (lo + hi) / 2
            // 乘积可达 1e10，必须先转 int64 再乘；用除法会因向下取整放宽阈值。
            if int64(potions[mid])*int64(v) >= success {
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        // lo 是第一个成功的下标，它右边（含自身）全部成功。
        ans[i] = m - lo
    }
    return ans
}

275. H 指数 II

第一个满足引用数与剩余论文数关系的位置。 有序数组中，下标越大引用数越高、剩余论文数越少；寻找第一个满足 citations[i] >= n - i 的下标，返回 n - i。

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int h = n - mid;

            if (citations[mid] == h) {
                return h;
            } else if (citations[mid] < h) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return n - left;
    }
}

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n-1

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

    return n - left
}

528. 按权重随机选择

随机数范围采用 [0, 总权重) 时，找第一个严格大于随机数的前缀和。

class Solution {
    private final int[] prefix;
    private final int total;

    public Solution(int[] w) {
        prefix = new int[w.length];
        int sum = 0;

        for (int i = 0; i < w.length; i++) {
            sum += w[i];
            prefix[i] = sum;
        }

        total = sum;
    }

    public int pickIndex() {
        int target = java.util.concurrent.ThreadLocalRandom.current().nextInt(total);

        int left = 0;
        int right = prefix.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (prefix[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

import "math/rand"

type Solution struct {
    prefix []int
    total  int
}

func Constructor(w []int) Solution {
    prefix := make([]int, len(w))
    sum := 0
    for i, weight := range w {
        sum += weight
        prefix[i] = sum
    }
    return Solution{prefix: prefix, total: sum}
}

func (this *Solution) PickIndex() int {
    target := rand.Intn(this.total)
    left, right := 0, len(this.prefix)-1

    for left < right {
        mid := left + (right-left)/2
        if this.prefix[mid] > target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

475. 供暖器

定位房屋左右相邻的供暖器。 先找第一个不小于房屋位置的供暖器，再比较它与前一个供暖器的距离；所有房屋所需距离的最大值就是答案。

class Solution {
    // 将供暖器位置排序后，对任意房屋，最近供暖器只可能在插入位置的左侧或右侧。
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int answer = 0;

        for (int house : houses) {
            int idx = lowerBound(heaters, house);
            int distance;

            if (idx == 0) {
                distance = heaters[0] - house;
            } else if (idx == heaters.length) {
                distance = house - heaters[heaters.length - 1];
            } else {
                int leftDistance = house - heaters[idx - 1];
                int rightDistance = heaters[idx] - house;

                distance = Math.min(leftDistance, rightDistance);
            }

            answer = Math.max(answer, distance);
        }

        return answer;
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

func findRadius(houses []int, heaters []int) int {
    // 将供暖器位置排序后，对任意房屋，最近供暖器只可能在插入位置的左侧或右侧。
    sort.Ints(heaters)
    answer := 0

    for _, house := range houses {
        idx := lowerBound475(heaters, house)
        distance := 0
        if idx == 0 {
            distance = heaters[0] - house
        } else if idx == len(heaters) {
            distance = house - heaters[len(heaters)-1]
        } else {
            leftDistance := house - heaters[idx-1]
            rightDistance := heaters[idx] - house
            if leftDistance < rightDistance {
                distance = leftDistance
            } else {
                distance = rightDistance
            }
        }

        if distance > answer {
            answer = distance
        }
    }

    return answer
}

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

    return left
}

补充题 219. 有序数组中绝对值最小的元素

以 0 为目标找分界点，再比较两侧元素的绝对值；注意分界点越界和最小整数取负溢出。

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;
        int 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 -(long) 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]
}

三、找右边界

统一思路：寻找最后一个满足条件的位置。满足条件时记录中点并继续向右，不满足时向左。下面的 <= target 可替换为题目对应的单调条件。

通用模板：找右边界

int left = 0;
int right = nums.length - 1;
int res = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] <= target) {
        // mid 满足条件，记下后继续向右找更靠后的
        res = 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 {
        // mid 满足条件，记下后继续向右找更靠后的
        res = mid
        left = mid + 1
    } else {
        right = mid - 1
    }
}
return res

69. x 的平方根

最后一个平方不超过目标值的整数。 平方随候选值增大而增大，满足限制时继续向右；比较时使用除法或宽整数，避免平方溢出。

class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }

        int left = 1;
        int right = x / 2;
        int ans = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }
}

func mySqrt(x int) int {
    if x < 2 {
        return x
    }

    left, right, ans := 1, x/2, 1
    for left <= right {
        mid := left + (right-left)/2
        if mid <= x/mid {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

441. 排列硬币

最后一个阶梯总数不超过硬币数量的行数。 用 k * (k + 1) / 2 <= n 判断前 k 行是否放得下，满足时继续找更大的 k。

// 核心实现：二分最大 k，维护必要状态并避免重复处理。
class Solution {
    public int arrangeCoins(int n) {
        long left = 0;
        long right = n;

        while (left < right) {
            long mid = (left + right + 1) / 2;
            long sum = mid * (mid + 1) / 2;

            if (sum <= n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return (int) left;
    }
}

// 核心实现：二分最大 k，维护必要状态并避免重复处理。
func arrangeCoins(n int) int {
    left := int64(0)
    right := int64(n)
    for left < right {
        mid := (left + right + 1) / 2
        sum := mid * (mid + 1) / 2
        if sum <= int64(n) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return int(left)
}

1146. 快照数组

最后一个不超过目标快照编号的记录。 每个下标按快照编号记录修改历史，查询时在该下标的有序历史中找右边界；同一快照内重复修改只保留最新值。

class SnapshotArray {
    private final List<int[]>[] history;
    private int snapId;

    public SnapshotArray(int length) {
        history = new List[length];

        for (int i = 0; i < length; i++) {
            history[i] = new ArrayList<>();
            history[i].add(new int[] {
                0,
                0
            });
        }
    }

    public void set(int index, int val) {
        List<int[]> records = history[index];
        int[] last = records.get(records.size() - 1);

        if (last[0] == snapId) {
            last[1] = val;
        } else {
            records.add(new int[] {
                snapId,
                val
            });
        }
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snap_id) {
        List<int[]> records = history[index];
        int left = 0;
        int right = records.size() - 1;

        while (left < right) {
            int mid = left + (right - left + 1) / 2;

            if (records.get(mid)[0] <= snap_id) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return records.get(left)[1];
    }
}

type record struct {
    snapID int
    value  int
}

type SnapshotArray struct {
    history [][]record
    snapID  int
}

func Constructor(length int) SnapshotArray {
    history := make([][]record, length)
    for i := range history {
        history[i] = []record{
            {snapID: 0, value: 0},
        }
    }
    return SnapshotArray{history: history}
}

func (this *SnapshotArray) Set(index int, val int) {
    records := this.history[index]
    last := len(records) - 1
    if records[last].snapID == this.snapID {
        records[last].value = val
        return
    }
    this.history[index] = append(records, record{snapID: this.snapID, value: val})
}

func (this *SnapshotArray) Snap() int {
    id := this.snapID
    this.snapID++
    return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    records := this.history[index]
    left, right := 0, len(records)-1
    for left < right {
        mid := left + (right-left+1)/2
        if records[mid].snapID <= snap_id {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return records[left].value
}

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

分别查找第一个和最后一个等于目标值的位置，组合左右边界。

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

四、缺失数量二分

统一思路：用数值与下标的差计算缺失数量，寻找累计缺失数量第一次达到 k 的位置，再还原缺失的数。

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

给定一个严格递增的正整数数组 nums 和一个正整数 k，从 nums[0] 开始，按从小到大的顺序找到第 k 个不在数组中的整数，并返回它。

示例 1：

输入：nums = [4,7,9,10], k = 1
输出：5
解释：从 4 开始，缺失的整数依次为 5、6、8、11……，第一个缺失的整数是 5。

示例 2：

输入：nums = [1,2,4], k = 3
输出：6
解释：缺失的整数依次为 3、5、6……，第三个缺失的整数是 6。

提示：

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^7
• 1 <= k <= 10^8
• nums 严格递增。

以数组第一个数为起点，缺失数量为 nums[i] - nums[0] - i。 缺失数量随下标单调不减，二分找到第一次达到 k 的位置，再从它前面的元素补足差额；答案在数组末尾之后时单独计算。

class Solution {
    // 如果最后一个元素之前缺失数量仍小于 k，答案在数组右侧，可以直接向后补差值。
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int missingLast = missing(nums, n - 1);

        if (missingLast < k) {
            return nums[n - 1] + k - missingLast;
        }

        int left = 0;
        int right = n - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (missing(nums, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        int before = missing(nums, left - 1);

        return nums[left - 1] + k - before;
    }

    private int missing(int[] nums, int index) {
        return nums[index] - nums[0] - index;
    }
}

func missingElement(nums []int, k int) int {
    // 如果最后一个元素之前缺失数量仍小于 k，答案在数组右侧，可以直接向后补差值。
    n := len(nums)
    missing := func(index int) int {
        return nums[index] - nums[0] - index
    }

    missingLast := missing(n - 1)
    if missingLast < k {
        return nums[n-1] + k - missingLast
    }

    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        if missing(mid) >= k {
            right = mid
        } else {
            left = mid + 1
        }
    }

    before := missing(left - 1)
    return nums[left-1] + k - before
}

1539. 第 k 个缺失的正整数

以 1 为起点，缺失数量为 arr[i] - i - 1。 二分找到缺失数量第一次达到 k 的位置，循环结束后的插入下标与 k 相加得到答案。

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0;
        // 右边界取 n 而非 n - 1，才容得下"答案落在数组末尾之后"的情况。
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            // 无缺失时 arr[mid] 应为 mid + 1，差值就是前面缺了几个正整数。
            int missing = arr[mid] - mid - 1;

            if (missing < k) {
                left = mid + 1;
            } else {
                // mid 本身就是候选，收缩时必须保留它。
                right = mid;
            }
        }

        // left 是答案之前仍然存在的数的个数，答案即第 left + k 个正整数。
        return left + k;
    }
}

func findKthPositive(arr []int, k int) int {
    left := 0
    // 右边界取 n 而非 n - 1，才容得下"答案落在数组末尾之后"的情况。
    right := len(arr)

    for left < right {
        mid := left + (right-left)/2
        // 无缺失时 arr[mid] 应为 mid + 1，差值就是前面缺了几个正整数。
        missing := arr[mid] - mid - 1

        if missing < k {
            left = mid + 1
        } else {
            // mid 本身就是候选，收缩时必须保留它。
            right = mid
        }
    }

    // left 是答案之前仍然存在的数的个数，答案即第 left + k 个正整数。
    return left + k
}

五、求最小可行答案

统一思路：判定结果随候选值增大，从不可行变为可行。中点可行时 right = mid，不可行时 left = mid + 1，找到最小可行值。

通用模板：最小可行答案

模板用于非负整数区间，且区间内至少有一个可行答案。可能无解时先判断上界是否可行；总复杂度需计入 check 的成本。

long firstFeasible(long left, long right, java.util.function.LongPredicate check) {
    while (left < right) {
        long mid = left + (right - left) / 2;

        if (check.test(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

func firstFeasible(left, right int64, check func(int64) bool) int64 {
    for left < right {
        mid := left + (right-left)/2
        if check(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

875. 爱吃香蕉的珂珂

给定速度，判断能否在规定时间内吃完。 每堆用时向上取整后求和。速度越大越容易完成，因此寻找满足时间限制的最小速度。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;

        for (int pile : piles) {
            right = Math.max(right, pile);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canFinish(int[] piles, int h, int speed) {
        long hours = 0;

        for (int pile : piles) {
            hours += (pile + speed - 1L) / speed;

            if (hours > h) {
                return false;
            }
        }

        return true;
    }
}

func minEatingSpeed(piles []int, h int) int {
    left, right := 1, 0
    for _, pile := range piles {
        if pile > right {
            right = pile
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canFinishBananas(piles, h, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canFinishBananas(piles []int, h, speed int) bool {
    var hours int64
    for _, pile := range piles {
        hours += (int64(pile) + int64(speed) - 1) / int64(speed)
        if hours > int64(h) {
            return false
        }
    }
    return true
}

1011. 在 D 天内送达包裹的能力

给定运力，判断能否在规定天数内运完。 按原顺序贪心装载，统计给定运力需要的天数；运力越大，天数越少，二分最小可行运力。

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;

        for (int weight : weights) {
            left = Math.max(left, weight);
            right += weight;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canShip(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canShip(int[] weights, int days, int capacity) {
        int usedDays = 1;
        int load = 0;

        for (int weight : weights) {
            // 当前天放不下时，必须开启新的一天。
            if (load + weight > capacity) {
                usedDays++;
                load = 0;

                if (usedDays > days) {
                    return false;
                }
            }

            load += weight;
        }

        return true;
    }
}

func shipWithinDays(weights []int, days int) int {
    left := 0
    right := 0
    for _, weight := range weights {
        if weight > left {
            left = weight
        }
        right += weight
    }

    for left < right {
        mid := left + (right-left)/2
        if canShip(weights, days, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canShip(weights []int, days int, capacity int) bool {
    usedDays := 1
    load := 0
    for _, weight := range weights {
        // 当前天放不下时，必须开启新的一天。
        if load+weight > capacity {
            usedDays++
            load = 0
            if usedDays > days {
                return false
            }
        }
        load += weight
    }
    return true
}

410. 分割数组的最大值

给定子段和上限，判断非负数组能否在限定段数内完成划分。 按给定上限贪心划分，统计所需段数。非负数组中，上限越大所需段数越少，因此查找最小可行上限。

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0;
        int right = 0;

        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canSplit(int[] nums, int k, int limit) {
        int parts = 1;
        int sum = 0;

        for (int num : nums) {
            if (sum + num > limit) {
                parts++;
                sum = num;

                if (parts > k) {
                    return false;
                }
            } else {
                sum += num;
            }
        }

        return true;
    }
}

func splitArray(nums []int, k int) int {
    left, right := 0, 0
    for _, num := range nums {
        if num > left {
            left = num
        }
        right += num
    }

    for left < right {
        mid := left + (right-left)/2
        if canSplit(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canSplit(nums []int, k, limit int) bool {
    parts, sum := 1, 0
    for _, num := range nums {
        if sum+num > limit {
            parts++
            sum = num
            if parts > k {
                return false
            }
        } else {
            sum += num
        }
    }
    return true
}

1482. 制作 m 束花所需的最少天数

给定天数，判断能否制作足够的花束。 扫描已盛开的连续花朵，遇到未盛开的花就中断连续计数。可制作花束数随天数增加而不减，因此二分最早可行日期。

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long) m * k > bloomDay.length) {
            return -1;
        }

        int left = bloomDay[0];
        int right = bloomDay[0];

        for (int day : bloomDay) {
            left = Math.min(left, day);
            right = Math.max(right, day);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canMake(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0;
        int consecutive = 0;

        for (int bloom : bloomDay) {
            if (bloom > day) {
                consecutive = 0;
                continue;
            }

            consecutive++;

            if (consecutive == k) {
                bouquets++;

                if (bouquets == m) {
                    return true;
                }

                consecutive = 0;
            }
        }

        return false;
    }
}

func minDays(bloomDay []int, m int, k int) int {
    if m > len(bloomDay)/k {
        return -1
    }

    left, right := bloomDay[0], bloomDay[0]
    for _, day := range bloomDay {
        if day < left {
            left = day
        }
        if day > right {
            right = day
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canMake(bloomDay, m, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

func canMake(bloomDay []int, m int, k int, day int) bool {
    bouquets := 0
    consecutive := 0

    for _, bloom := range bloomDay {
        if bloom > day {
            consecutive = 0
            continue
        }

        consecutive++
        if consecutive == k {
            bouquets++
            if bouquets == m {
                return true
            }
            consecutive = 0
        }
    }

    return false
}

六、求最大可行答案

统一思路：判定结果随候选值增大，从可行变为不可行。中点可行时 left = mid，不可行时 right = mid - 1；中点必须上取整，避免两个候选时不收缩。

通用模板：最大可行答案

模板用于非负整数区间，且区间内至少有一个可行答案。可能无解时先判断下界；计算中点和判定中的求和、乘积都要考虑溢出。

long lastFeasible(long left, long right, java.util.function.LongPredicate check) {
    while (left < right) {
        long distance = right - left;
        long mid = left + distance / 2 + distance % 2;

        if (check.test(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

func lastFeasible(left, right int64, check func(int64) bool) int64 {
    for left < right {
        distance := right - left
        mid := left + distance/2 + distance%2
        if check(mid) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

1552. 两球之间的磁力

给定最小间距，判断能否放满所有球。 先排序位置，再从左到右贪心放球；间距越大越难放满，因此寻找最大可行间距。

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);

        int left = 1;
        int right = position[position.length - 1] - position[0];

        while (left < right) {
            int mid = left + (right - left + 1) / 2;

            if (canPlace(position, m, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean canPlace(int[] position, int balls, int distance) {
        int placed = 1;
        int last = position[0];

        for (int i = 1; i < position.length; i++) {
            if (position[i] - last >= distance) {
                placed++;
                last = position[i];

                if (placed == balls) {
                    return true;
                }
            }
        }

        return placed >= balls;
    }
}

import "sort"

func maxDistance(position []int, m int) int {
    sort.Ints(position)

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

func canPlace(position []int, balls int, distance int) bool {
    placed := 1
    last := position[0]
    for i := 1; i < len(position); i++ {
        if position[i]-last >= distance {
            placed++
            last = position[i]
            if placed == balls {
                return true
            }
        }
    }
    return placed >= balls
}

木头切割问题

给定段长，判断 sum(木头长度 / 段长) >= k 是否成立；段长从 1 开始，不能除以 0。

class Solution {
    public int woodCut(int[] woods, int k) {
        int right = 0;

        for (int wood : woods) {
            right = Math.max(right, wood);
        }

        int left = 1;
        int ans = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (canCut(woods, k, mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }

    private boolean canCut(int[] woods, int k, int len) {
        long count = 0;

        for (int wood : woods) {
            count += wood / len;

            if (count >= k) {
                return true;
            }
        }

        return false;
    }
}

func woodCut(woods []int, k int) int {
    right := 0
    for _, wood := range woods {
        if wood > right {
            right = wood
        }
    }

    left, ans := 1, 0
    for left <= right {
        mid := left + (right-left)/2
        if canCutWood(woods, k, mid) {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

func canCutWood(woods []int, k, length int) bool {
    var count int64
    for _, wood := range woods {
        count += int64(wood / length)
        if count >= int64(k) {
            return true
        }
    }
    return false
}

七、第 K 小值：计数二分

统一思路：对值域二分。定义 count(x) 为不超过 x 的元素或组合数量，寻找第一个使 count(x) >= k 成立的值；边界收缩与“求最小可行答案”一致。

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

统计矩阵中不超过候选值的元素个数。 计数随候选值增大而不减，寻找第一个使计数达到 k 的值；利用行列有序进行阶梯计数。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (countLessOrEqual(matrix, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private int countLessOrEqual(int[][] matrix, int target) {
        int n = matrix.length;
        int row = n - 1;
        int col = 0;
        int count = 0;

        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }

        return count;
    }
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    left := matrix[0][0]
    right := matrix[n-1][n-1]

    for left < right {
        mid := left + (right-left)/2
        if countLessOrEqual(matrix, mid) >= k {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func countLessOrEqual(matrix [][]int, target int) int {
    n := len(matrix)
    row := n - 1
    col := 0
    count := 0
    for row >= 0 && col < n {
        if matrix[row][col] <= target {
            count += row + 1
            col++
        } else {
            row--
        }
    }
    return count
}

668. 乘法表中第k小的数

统计乘法表中不超过候选值的元素个数。 第 i 行的贡献为 min(列数, x / i)，累加后判断是否达到 k，据此收缩值域。

class Solution {
    // 值 x 作为阈值时，可以快速算出表中有多少个数不超过 x，用这个计数函数做二分查找。
    public int findKthNumber(int m, int n, int k) {
        long left = 1;
        long right = (long) m * n;

        while (left < right) {
            long mid = left + (right - left) / 2;

            if (countLE(mid, m, n) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (int) left;
    }

    private long countLE(long x, int m, int n) {
        long total = 0;

        for (int i = 1; i <= m; i++) {
            total += Math.min(n, (int) (x / i));

            if (total > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
        }

        return total;
    }
}

func findKthNumber(m int, n int, k int) int {
    // 值 x 作为阈值时，可以快速算出表中有多少个数不超过 x，用这个计数函数做二分查找。
    left := int64(1)
    right := int64(m) * int64(n)
    for left < right {
        mid := left + (right-left)/2
        if countLE(mid, m, n) >= int64(k) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return int(left)
}

func countLE(x int64, m int, n int) int64 {
    var total int64
    for i := 1; i <= m; i++ {
        c := int(x / int64(i))
        if c > n {
            c = n
        }
        total += int64(c)
    }
    return total
}

719. 找出第 K 小的数对距离

统计距离不超过候选值的数对数量。 数组排序后，用双指针统计距离不超过 mid 的数对；计数达到 k 时向更小的距离查找。

// 对距离进行二分，判断有多少对距离 <= d。
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 0;
        int high = nums[nums.length - 1] - nums[0];

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (countPairs(nums, mid) >= k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }

    private int countPairs(int[] nums, int dist) {
        int count = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            while (nums[right] - nums[left] > dist) {
                left++;
            }

            count += right - left;
        }

        return count;
    }
}

// 对距离进行二分，判断有多少对距离 <= d。
func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    low := 0
    high := nums[len(nums)-1] - nums[0]

    for low < high {
        mid := low + (high-low)/2
        if countPairs(nums, mid) >= k {
            high = mid
        } else {
            low = mid + 1
        }
    }

    return low
}

func countPairs(nums []int, dist int) int {
    count := 0
    left := 0

    for right := 0; right < len(nums); right++ {
        for nums[right]-nums[left] > dist {
            left++
        }
        count += right - left
    }

    return count
}

287. 寻找重复数

统计 <= x 的元素个数，利用 count(x) > x 定位重复值；判定阈值随 x 变化，不是固定的 k。

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;

            for (int value : nums) {
                if (value <= mid) {
                    count++;
                }
            }

            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

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

八、旋转数组找目标

统一思路：先判断哪一半有序，再根据目标值是否落在这段有序区间内决定保留哪半。重复元素可能让方向无法判断，此时需要缩小相等的边界，最坏退化到 $O(n)$。

33. 搜索旋转排序数组

无重复元素。 每轮先判断哪半有序，再判断目标是否落在该有序区间内，只保留可能包含目标的一半。

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

81. 搜索旋转排序数组 II

包含重复元素。 先排除使方向无法判断的相等边界，再判断有序半区；重复元素过多时最坏退化到线性扫描。

class Solution {
    // 重复元素会让 nums[mid] == nums[right] 时无法判断哪边有序，此时只能收缩 right 去掉一。
    public boolean 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 true;
            }

            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] > nums[right]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                right--;
            }
        }

        return false;
    }
}

func search(nums []int, target int) bool {
    // 重复元素会让 nums[mid] == nums[right] 时无法判断哪边有序，此时只能收缩 right 去掉一。
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }

        if nums[mid] < nums[right] {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else if nums[mid] > nums[right] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            right--
        }
    }

    return false
}

面试题 10.03. 搜索旋转数组

还要求返回最小匹配下标，不能直接返回任意命中位置。

class Solution {
    public int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // 左端点命中即是最小下标，区间左侧已被证明不含 target。
            if (arr[left] == target) {
                return left;
            }

            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                // 左边可能还有更早的出现位置，只收缩右边界。
                right = mid;
            } else if (arr[mid] > arr[left]) {
                if (arr[left] < target && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (arr[mid] < arr[left]) {
                if (arr[mid] < target && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                // 重复值遮蔽有序区间时，只能安全地丢掉一个左端点。
                left++;
            }
        }

        return -1;
    }
}

func search(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    for left <= right {
        // 左端点命中即是最小下标。
        if arr[left] == target {
            return left
        }

        mid := left + (right-left)/2
        if arr[mid] == target {
            // 继续向左找更小的下标。
            right = mid
        } else if arr[mid] > arr[left] {
            if arr[left] < target && target < arr[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else if arr[mid] < arr[left] {
            if arr[mid] < target && target <= arr[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else {
            // 无法判断有序侧，只丢掉一个左端点。
            left++
        }
    }
    return -1
}

九、旋转数组找最小值

统一思路：比较 nums[mid] 与 nums[right]。中点更大时最小值在右侧，令 left = mid + 1；中点更小时保留中点，令 right = mid。包含重复值且两者相等时，使用 right--。

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

比较中点与右端点的值：中点更大时最小值在右半，令 left = mid + 1；否则保留中点，令 right = mid，直到区间收敛。

class Solution {
    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];
    }
}

func findMin(nums []int) int {
    left := 0
    right := len(nums) - 1

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

    return nums[left]
}

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

允许重复值，最坏退化到 $O(n)$。 中点与右端点相等时无法确定最小值在哪边，缩小右边界；其余情况按照两者的大小关系进行二分。

class Solution {
    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 if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                // 重复值无法判断方向，安全丢弃一个右端点。
                right--;
            }
        }

        return nums[left];
    }
}

func findMin(nums []int) int {
    left := 0
    right := 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 {
            // 相等时无法排除 mid，只缩小 right。
            right--
        }
    }
    return nums[left]
}

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

与 154 同一类。 比较中点与右端点决定保留哪半；相等时仅缩小右边界，避免把最小值排除。

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else if (numbers[mid] < numbers[right]) {
                right = mid;
            } else {
                right--;
            }
        }

        return numbers[left];
    }
}

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

十、峰值查找

统一思路：比较中点与右邻居。上坡时保留右半，下坡时保留左半及中点。依据是“保留下来的一半必有峰值”，不是数组整体有序。模板假设数组非空、相邻元素不相等，边界外视为负无穷。

通用模板：峰值查找

int left = 0;
int right = nums.length - 1;

while (left < right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] > nums[mid + 1]) {
        // 下坡，峰值在左侧（含 mid）
        right = 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] {
        // 下坡，峰值在左侧（含 mid）
        right = mid
    } else {
        // 上坡，峰值在右侧
        left = mid + 1
    }
}
return left

162. 寻找峰值

比较 nums[mid] 与 nums[mid + 1]。上坡时右半必有峰值，下坡时左半连同中点必有峰值，始终保留包含峰值的一半。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 朝更高的一侧收缩，峰值一定存在于该侧。
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

func findPeakElement(nums []int) int {
    left := 0
    right := len(nums) - 1

    for left < right {
        mid := left + (right-left)/2
        // mid 和 mid+1 的坡度决定峰值所在方向。
        if nums[mid] < nums[mid+1] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return left
}

852. 山脉数组的峰顶索引

山脉数组先升后降，峰顶唯一。比较中点与右邻居，沿上坡方向收缩左边界，沿下坡方向收缩右边界，最终定位峰顶。

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

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

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

先找峰顶，再分别在升序段、降序段精确查找。 优先查找左侧升序段，以满足返回最小下标的要求；同时注意接口调用次数限制。

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        int left = 0;
        int right = n - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            int value = mountainArr.get(mid);
            int nextValue = mountainArr.get(mid + 1);

            if (value < nextValue) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        int peak = left;
        int ans = binarySearch(mountainArr, 0, peak, target, true);

        if (ans != -1) {
            return ans;
        }

        return binarySearch(mountainArr, peak + 1, n - 1, target, false);
    }

    private int binarySearch(
            MountainArray mountainArr, int left, int right, int target, boolean asc) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = mountainArr.get(mid);

            if (value == target) {
                return mid;
            }

            // 升序和降序区间的移动方向相反。
            if ((asc && value < target) || (!asc && value > target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

func findInMountainArray(target int, mountainArr *MountainArray) int {
    n := mountainArr.length()
    left := 0
    right := n - 1
    for left < right {
        mid := left + (right-left)/2
        value := mountainArr.get(mid)
        nextValue := mountainArr.get(mid + 1)
        if value < nextValue {
            left = mid + 1
        } else {
            right = mid
        }
    }

    peak := left
    ans := searchMountain(mountainArr, 0, peak, target, true)
    if ans != -1 {
        return ans
    }
    return searchMountain(mountainArr, peak+1, n-1, target, false)
}

func searchMountain(arr *MountainArray, left int, right int, target int, asc bool) int {
    for left <= right {
        mid := left + (right-left)/2
        value := arr.get(mid)
        if value == target {
            return mid
        }
        // asc 标识当前区间是升序还是降序。
        if (asc && value < target) || (!asc && value > target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

十一、维护有序辅助数组

统一思路：维护 tails，其中第 i 项是长度为 i + 1 的递增子序列能取得的最小末尾值。对每个新值二分查找第一个不小于它的位置，替换或追加；二分发生在 tails 中，不是原数组中。

300. 最长递增子序列

维护递增的 tails 数组，记录每种子序列长度对应的最小末尾值。对新元素二分找到第一个不小于它的位置并替换，超出末尾则追加；最终长度就是答案。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int left = 0;
            int right = size;

            while (left < right) {
                int mid = left + (right - left) / 2;

                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = num;

            if (left == size) {
                size++;
            }
        }

        return size;
    }
}

func lengthOfLIS(nums []int) int {
    tails := make([]int, len(nums))
    size := 0

    for _, num := range nums {
        left, right := 0, size
        for left < right {
            mid := left + (right-left)/2
            if tails[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }

        tails[left] = num
        if left == size {
            size++
        }
    }
    return size
}

354. 俄罗斯套娃信封问题

宽度升序、同宽高度降序，再对高度应用 LIS。 同宽高度降序可以防止相同宽度的信封被计入递增子序列，然后用二分维护高度的 tails。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(
                envelopes,
                (first, second) -> {
                    if (first[0] != second[0]) {
                        return Integer.compare(first[0], second[0]);
                    }

                    return Integer.compare(second[1], first[1]);
                });

        int[] tails = new int[envelopes.length];
        int size = 0;

        for (int[] envelope : envelopes) {
            int height = envelope[1];
            int left = 0;
            int right = size;

            while (left < right) {
                int mid = left + (right - left) / 2;

                if (tails[mid] < height) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = height;

            if (left == size) {
                size++;
            }
        }

        return size;
    }
}

import "sort"

func maxEnvelopes(envelopes [][]int) int {
    sort.Slice(envelopes, func(i int, j int) bool {
        if envelopes[i][0] != envelopes[j][0] {
            return envelopes[i][0] < envelopes[j][0]
        }
        return envelopes[i][1] > envelopes[j][1]
    })

    tails := make([]int, 0, len(envelopes))
    for _, envelope := range envelopes {
        height := envelope[1]
        left, right := 0, len(tails)
        for left < right {
            mid := left + (right-left)/2
            if tails[mid] < height {
                left = mid + 1
            } else {
                right = mid
            }
        }
        if left == len(tails) {
            tails = append(tails, height)
        } else {
            tails[left] = height
        }
    }
    return len(tails)
}

十二、配对下标规律

统一思路：单一元素之前，重复元素从偶数下标开始成对；之后配对位置错开。比较 nums[mid] 与 nums[mid ^ 1]，相等则向右，否则保留左半及中点。

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

单一元素前后的配对下标规律不同。用 mid ^ 1 找到中点的配对下标：两值相等时向右查找，否则保留左半及中点，直到只剩一个位置。

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int 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]
}

十三、双数组划分

统一思路：在较短数组上二分划分位置，另一数组的划分位置由左半元素总数确定；根据两侧边界值调整划分，直到左半最大值不大于右半最小值。

4. 寻找两个正序数组的中位数

在较短数组中二分划分位置，另一数组的划分位置由左半元素总数决定。根据两侧交叉边界值移动划分，直到左半最大值不大于右半最小值，再按总长度奇偶计算中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int leftSize = (m + n + 1) / 2;
        int left = 0;
        int right = m;

        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = leftSize - i;
            // 划分在数组边界时，用虚拟极值统一比较四个边界。
            int nums1Left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1Right = i == m ? Integer.MAX_VALUE : nums1[i];
            int nums2Left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2Right = j == n ? Integer.MAX_VALUE : nums2[j];

            if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
                int leftMax = Math.max(nums1Left, nums2Left);

                if ((m + n) % 2 == 1) {
                    return leftMax;
                }

                int rightMin = Math.min(nums1Right, nums2Right);

                return ((double) leftMax + rightMin) / 2.0;
            }

            if (nums1Left > nums2Right) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }

        return 0.0;
    }
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }

    m := len(nums1)
    n := len(nums2)
    leftSize := (m + n + 1) / 2
    left := 0
    right := m

    for left <= right {
        i := left + (right-left)/2
        j := leftSize - i
        // 划分在数组边界时，用虚拟极值统一比较四个边界。
        nums1Left := -1 << 60
        nums1Right := 1 << 60
        nums2Left := -1 << 60
        nums2Right := 1 << 60

        if i > 0 {
            nums1Left = nums1[i-1]
        }
        if i < m {
            nums1Right = nums1[i]
        }
        if j > 0 {
            nums2Left = nums2[j-1]
        }
        if j < n {
            nums2Right = nums2[j]
        }

        if nums1Left <= nums2Right && nums2Left <= nums1Right {
            leftMax := maxInt(nums1Left, nums2Left)
            if (m+n)%2 == 1 {
                return float64(leftMax)
            }

            rightMin := minInt(nums1Right, nums2Right)
            return (float64(leftMax) + float64(rightMin)) / 2.0
        }

        if nums1Left > nums2Right {
            right = i - 1
        } else {
            left = i + 1
        }
    }

    return 0.0
}

func minInt(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2020/94980842

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！