二分查找变体

📌 核心思想

二分查找不只用于“在有序数组中找某个值”，更常见的用法是利用单调性缩小答案范围。

常见变体：

1. 标准查找：查找目标值是否存在
2. 边界查找：查找第一个或最后一个满足条件的位置
3. 旋转数组查找：一半有序、一半无序
4. 二分答案：答案空间具有单调性
5. 浮点二分：连续答案逼近

🎯 适用条件

1. 有序性

数组本身有序，或者可以通过某种规则判断目标在左半还是右半。

典型题目：

• LeetCode 704 二分查找
• LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
• LeetCode 33 搜索旋转排序数组

2. 单调性

存在一个判断函数 check(x)，使得答案空间呈现如下结构：

False False False True True True

或者：

True True True False False False

典型题目：

• LeetCode 875 爱吃香蕉的珂珂
• LeetCode 1011 在 D 天内送达包裹的能力
• LeetCode 410 分割数组的最大值

💻 模板一：寻找第一个满足条件的位置

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

含义：

• 返回第一个 nums[i] >= target 的位置
• 若所有元素都小于 target，返回 len(nums)
• 可用于插入位置、左边界、计数等问题

💻 模板二：寻找最后一个满足条件的位置

func upperBoundLast(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 - 1
}

含义：

• 返回最后一个 nums[i] <= target 的位置
• 若所有元素都大于 target，返回 -1

💻 模板三：二分答案

🎞️ 二分答案动画

（附件 binary-answer.svg 未随站点发布）

动画表达的是“可行性边界”：左侧是 False，右侧是 True，目标是找第一个 True。

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

关键点：

• check(mid) 表示当前答案是否可行
• 如果要找“最小可行值”，可行时收缩右边界
• 如果要找“最大可行值”，通常反过来设计 check

🔍 例题：爱吃香蕉的珂珂

func minEatingSpeed(piles []int, h int) int {
    canFinish := func(speed int) bool {
        hours := 0
        for _, pile := range piles {
            hours += (pile + speed - 1) / speed
        }
        return hours <= h
    }
 
    right := piles[0]
    for _, pile := range piles[1:] {
        if pile > right {
            right = pile
        }
    }
    left := 1
    for left < right {
        mid := left + (right-left)/2
        if canFinish(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

单调性：

• 速度越快，耗时越少
• 如果速度 x 可以完成，那么所有大于 x 的速度都可以完成
• 因此可以二分最小可行速度

⚠️ 常见错误

问题	原因	处理方式
死循环	left 和 right 没有收缩	使用半开区间或统一模板
边界少 1	返回值含义不清楚	明确找第一个还是最后一个
二分答案无法判断	没有找到单调性	先写出 check(x)
旋转数组判断错误	没区分哪一半有序	每次先判断左半或右半是否有序

🧠 判断流程

1. 题目是否有序，或答案是否有单调性？
2. 要找的是目标值、左边界、右边界，还是最优答案？
3. check(mid) 的真假分布是什么？
4. 返回 left、right 还是 left - 1？

🔗 相关笔记

• 标准二分查找
• 左边界查找
• 右边界查找
• 二分查找模板

---

返回：搜索算法