二分查找

#算法 · #二分查找 · #旋转数组 · #二分答案 · #边界处理

二分查找看似简单，实则变体极多，细节魔鬼。左闭右闭还是左闭右开？等于 target 要不要继续？旋转数组怎么搜？二分答案怎么用？一道看似 5 分钟写完的题，可能藏着 10 个坑。

1. 核心思想

二分查找的本质是：在有序区间上，每次排除一半候选，将 O(n) 降为 O(log n)。

mermaid

flowchart TB
    A["区间 [L, R]"] --> B{"mid 的值? vs target"}
    B -->|"< target"| C["排除 [L, mid]<br/>L = mid + 1"]
    B -->|"> target"| D["排除 [mid, R]<br/>R = mid - 1"]
    B -->|"== target"| E["找到！"]
    C --> F{"L > R?"}
    D --> F
    F -->|"否"| B
    F -->|"是"| G["未找到"]

1.1 循环不变量

二分查找最关键的概念是循环不变量（Loop Invariant）——在每次循环开始和结束时保持不变的命题。

错误的根源：循环不变量不一致。比如区间定义是 [L, R)，但循环条件和更新用的是 [L, R] 的逻辑。

2. 三种区间写法

2.1 左闭右闭 `[L, R]`

func binarySearch(nums []int, target int) int {
    L, R := 0, len(nums)-1
    for L <= R {
        mid := L + (R-L)/2   // 防溢出
        if nums[mid] < target {
            L = mid + 1       // target 在右侧
        } else if nums[mid] > target {
            R = mid - 1       // target 在左侧
        } else {
            return mid
        }
    }
    return -1
}

要素	取值
初始区间	`[0, n-1]`
循环条件	`L <= R`（区间非空）
中值	`L + (R-L)/2`
目标在右	`L = mid + 1`
目标在左	`R = mid - 1`

2.2 左闭右开 `[L, R)`

func binarySearch2(nums []int, target int) int {
    L, R := 0, len(nums)
    for L < R {                   // 注意：L < R, 不是 L <= R
        mid := L + (R-L)/2
        if nums[mid] < target {
            L = mid + 1
        } else if nums[mid] > target {
            R = mid               // 注意：不是 mid - 1
        } else {
            return mid
        }
    }
    return -1
}

2.3 推荐写法

推荐 [L, R]（左闭右闭），原因：

对称性好，不容易混淆
R = mid - 1 和 L = mid + 1 对称
循环条件 L <= R 直观（区间还有元素就继续）

3. 经典变体

3.1 查找左边界（第一个等于 target 的位置）

func searchLeft(nums []int, target int) int {
    L, R := 0, len(nums)-1
    for L <= R {
        mid := L + (R-L)/2
        if nums[mid] < target {
            L = mid + 1
        } else {
            // nums[mid] >= target 时收缩右边界
            R = mid - 1
        }
    }
    // 循环结束后，L 指向第一个 >= target 的位置
    if L < len(nums) && nums[L] == target {
        return L
    }
    return -1
}

关键理解：当 nums[mid] >= target 时，统一收缩 R，即使 nums[mid] == target 也不返回。循环结束后 L 就是答案。

3.2 查找右边界（最后一个等于 target 的位置）

func searchRight(nums []int, target int) int {
    L, R := 0, len(nums)-1
    for L <= R {
        mid := L + (R-L)/2
        if nums[mid] <= target {
            // nums[mid] <= target 时统一推进 L
            L = mid + 1
        } else {
            R = mid - 1
        }
    }
    // 循环结束后，R 指向最后一个 <= target 的位置
    if R >= 0 && nums[R] == target {
        return R
    }
    return -1
}

3.3 查找插入位置

// 查找 target 应插入的位置（第一个 >= target 的位置）
func searchInsert(nums []int, target int) int {
    L, R := 0, len(nums)-1
    for L <= R {
        mid := L + (R-L)/2
        if nums[mid] < target {
            L = mid + 1
        } else {
            R = mid - 1
        }
    }
    return L  // 无论 target 是否存在，L 就是插入位置
}

3.4 旋转排序数组搜索

// 搜索旋转排序数组（如 [4,5,6,7,0,1,2] 中搜 0）
func searchRotated(nums []int, target int) int {
    L, R := 0, len(nums)-1
    for L <= R {
        mid := L + (R-L)/2
        if nums[mid] == target {
            return mid
        }
        // 判断哪一半是有序的
        if nums[L] <= nums[mid] {  // 左半有序
            if nums[L] <= target && target < nums[mid] {
                R = mid - 1   // target 在左半
            } else {
                L = mid + 1   // target 在右半
            }
        } else {                     // 右半有序
            if nums[mid] < target && target <= nums[R] {
                L = mid + 1   // target 在右半
            } else {
                R = mid - 1   // target 在左半
            }
        }
    }
    return -1
}

3.5 寻找峰值

// 峰值元素指大于左右相邻元素的值，nums[i] ≠ nums[i+1]
func findPeakElement(nums []int) int {
    L, R := 0, len(nums)-1
    for L < R {
        mid := L + (R-L)/2
        if nums[mid] > nums[mid+1] {
            // 在下降坡：峰值在左（含 mid）
            R = mid
        } else {
            // 在上升坡：峰值在右（不含 mid）
            L = mid + 1
        }
    }
    return L
}

4. 二分答案

当问题满足单调性时，可以对答案进行二分，将"求最优解"转化为"判断是否可行"。

二分答案 = 二分查找 + 可行性判定函数

4.1 模板

// 二分答案模板：求满足条件的最小值 / 最大值
func binaryAnswer() int {
    L, R := 答案的最小可能值, 答案的最大可能值
    for L <= R {
        mid := L + (R-L)/2
        if check(mid) {   // mid 可行
            // 保存答案，尝试更优
            R = mid - 1   // 找更小的
        } else {
            L = mid + 1   // mid 不可行
        }
    }
    return ans
}

4.2 经典问题

问题	二分什么	check 判断
分割数组的最大值	最大子数组和	能否分成 m 个子数组，每段和 ≤ mid
Koko 吃香蕉	吃香蕉速度 k	以速度 k 能否在 h 小时内吃完
第 K 小的距离对	距离值 d	距离 ≤ d 的对数是否 ≥ k
H 指数 II	h 值	是否有 h 篇论文被引用 ≥ h 次

4.3 示例：爱吃香蕉的 Koko

func minEatingSpeed(piles []int, h int) int {
    L, R := 1, 0
    for _, p := range piles {
        if p > R {
            R = p
        }
    }

    canFinish := func(speed int) bool {
        hours := 0
        for _, p := range piles {
            hours += (p + speed - 1) / speed  // 向上取整
        }
        return hours <= h
    }

    for L < R {
        mid := L + (R-L)/2
        if canFinish(mid) {
            R = mid   // 可以再慢一点
        } else {
            L = mid + 1
        }
    }
    return L
}

4.4 浮点数二分

浮点数二分与整数二分的最大区别：不需要担心边界 ±1，但需要设置精度终止条件。

// 浮点数二分模板：求平方根
func sqrtFloat(x float64) float64 {
    L, R := 0.0, x
    if x < 1 {
        R = 1.0  // 小于 1 时平方根大于自身，如 sqrt(0.25) = 0.5 > 0.25
    }

    // 方法1：固定迭代次数（推荐，稳定）
    for i := 0; i < 100; i++ { // 100 次迭代精度可达 ~2⁻¹⁰⁰
        mid := (L + R) / 2
        if mid*mid < x {
            L = mid
        } else {
            R = mid
        }
    }
    return L
}

// 方法2：精度控制
func sqrtFloatEps(x, eps float64) float64 {
    L, R := 0.0, x
    if x < 1 {
        R = 1.0
    }
    for R-L > eps {
        mid := (L + R) / 2
        if mid*mid < x {
            L = mid
        } else {
            R = mid
        }
    }
    return (L + R) / 2
}

整数二分	浮点数二分
`L = mid + 1` / `R = mid - 1`	`L = mid` / `R = mid`（不能 ±1！）
循环条件 `L <= R`	循环条件 `R - L > eps` 或固定迭代次数
边界精确	有精度误差
O(log₂ N) 精确次数	迭代 60 次 ≈ 浮点 2⁻⁶⁰ 精度，100 次 ≈ 2⁻¹⁰⁰

4.5 三分查找——搜索单峰函数的最值

当函数是单峰（unimodal）而非单调时，二分不适用——需要三分查找。

场景：凸函数求最小值 / 凹函数求最大值（如抛物线、凸优化问题）。

mermaid

flowchart LR
    subgraph Convex["凸函数 f(x) — 求最小值"]
        direction LR
        A["L"] --> B["m1"] --> C["m2"] --> D["R"]
    end
    ConvexDesc["f(m1) < f(m2): 最小值在 [L, m2] → R = m2"]
    ConvexDesc2["f(m1) > f(m2): 最小值在 [m1, R] → L = m1"]
    ConvexDesc3["f(m1) = f(m2): 最小值在 [m1, m2]"]

// 三分查找：单峰数组找拐点（先增后减找峰值）
func ternarySearch(arr []int) int {
    L, R := 0, len(arr)-1
    for R-L > 2 {                    // 剩余 ≤ 3 个元素时直接比较
        m1 := L + (R-L)/3
        m2 := R - (R-L)/3
        if arr[m1] < arr[m2] {
            L = m1                   // 峰值在右侧
        } else {
            R = m2                   // 峰值在左侧
        }
    }
    // 在 [L, R] 中找最大值（最多 3 个元素）
    maxIdx := L
    for i := L + 1; i <= R; i++ {
        if arr[i] > arr[maxIdx] {
            maxIdx = i
        }
    }
    return maxIdx
}

// 浮点数三分：求凸函数 f(x) 的最小值
func ternarySearchFloat(f func(float64) float64, L, R float64) float64 {
    for i := 0; i < 100; i++ {
        m1 := L + (R-L)/3
        m2 := R - (R-L)/3
        if f(m1) < f(m2) {
            R = m2      // 最小值靠左
        } else {
            L = m1      // 最小值靠右
        }
    }
    return (L + R) / 2
}

三分 vs 二分区别：

特性	二分查找	三分查找
适用条件	单调序列	单峰/单谷函数
每次缩减	1/2	1/3
比较次数/迭代	1 次	2 次
总效率	log₂N	2 × log₁.₅N ≈ 3.4 × log₂N
典型问题	有序数组搜索	抛物线求极值、凸优化

5. 边界条件速查表

场景	区间	循环条件	左更新	右更新	返回值
基础搜索	`[0, n-1]`	`L <= R`	`L = mid+1`	`R = mid-1`	`mid`
左边界	`[0, n-1]`	`L <= R`	`L = mid+1`	`R = mid-1`	`L`
右边界	`[0, n-1]`	`L <= R`	`L = mid+1`	`R = mid-1`	`R`
插入位置	`[0, n-1]`	`L <= R`	`L = mid+1`	`R = mid-1`	`L`
峰值	`[0, n-1]`	`L < R`	`L = mid+1`	`R = mid`	`L` 或 `R`
二分答案	视问题	`L <= R`	视问题	视问题	`ans`

6. 常见错误

错误	说明	修复
`mid = (L+R)/2`	L+R 可能溢出（C/C++/Java）	`mid = L + (R-L)/2`
无限循环	`L = mid` 而不 `L = mid+1`，且 `mid` 向下取整	确保每次区间缩小
循环条件错误	混淆 `L < R` 和 `L <= R`	始终遵循区间定义
返回值错误	左边界返回了 `mid`	理解 `L`/`R` 的最终含义
变体混淆	用基础搜索的 `return mid` 写左边界	分清场景再动笔

7. 工程中的二分思想

场景	二分应用
Git Bisect	`git bisect` 用二分查找定位引入 Bug 的 commit
数据库 B+Tree 查找	每一层的页内查找都是二分（页内 key 有序）
GC 分代阈值	调整 GC 触发阈值的二分探索
Kafka 日志查找	offset 查找先用时间戳二分定位 segment 文件
TCP 拥塞控制	慢启动阶段 cwnd 指数增长，本质是"二分探测"网络容量

7.1 详解：B+Tree 页内二分搜索

B+Tree 是 MySQL InnoDB 的核心索引结构，每一层查找都包含页内二分和跨页跳转：

一个 B+Tree 查找的完整过程（查询 key=42，3 层树）：

第 2 层（根节点，页 100）:
  keys: [20, 50, 80]
  → 页内二分: 20 < 42 ≤ 50 → 走 child[1] → 页 200

第 1 层（内部节点，页 200）:
  keys: [25, 35, 42, 47]
  → 页内二分: 42 == 42 → 走 child[3] → 页 300

第 0 层（叶子节点，页 300）:
  keys: [40, 41, 42, 42, 43, 44]
  → 页内二分: 找到 42 的第一个位置 → 返回对应行数据

为什么页内用二分而不是 B 树自带的"指针跟随"？

B+Tree 的每个页（默认 16KB）内存储了数百个 key。
页内 key 是有序数组，二分查找 O(log₂ 键数) 只需要 ~10 次比较。
如果改用线性扫描，平均要扫键数/2 次（数十到上百次）。

但实际 InnoDB 用了"优化版二分"——自适应哈希：
  对于热点查询（如根据主键 ID 查单行），InnoDB 在缓冲池中建立
  哈希索引直接 O(1) 定位，跳过页内二分。

B+Tree 查找的性能估算：

假设：
  - 每页 16KB
  - 主键 BIGINT (8B) + 指针 (6B) = 14B/条
  - 每页约 16KB / 14B ≈ 1170 条记录
  - 叶子节点每行 200B → 每页约 80 行

3 层 B+Tree:
  根节点 1 页 × 1170 → 第 2 层 1170 页 × 1170 → 叶子层约 137 万页
  → 能存储 137万页 × 80行/页 ≈ 1 亿行

查找一条记录: 2 次页内二分 + 1 次叶子页二分 = 3 次二分
每次页内二分 ~10 次比较（log₂ 1170 ≈ 10）
总比较次数: 30 次 ← 这就是为什么 B+Tree 能做到 O(log N)!

实际 IO: 3 次随机读（每层一次），如果是热数据在缓冲池中则是 3 次内存查找

二分查找

1. 核心思想

1.1 循环不变量

2. 三种区间写法

2.1 左闭右闭 `[L, R]`

2.2 左闭右开 `[L, R)`

2.3 推荐写法

3. 经典变体

3.1 查找左边界（第一个等于 target 的位置）

3.2 查找右边界（最后一个等于 target 的位置）

3.3 查找插入位置

3.4 旋转排序数组搜索

3.5 寻找峰值

4. 二分答案

4.1 模板

4.2 经典问题

4.3 示例：爱吃香蕉的 Koko

4.4 浮点数二分

4.5 三分查找——搜索单峰函数的最值

5. 边界条件速查表

6. 常见错误

7. 工程中的二分思想

7.1 详解：B+Tree 页内二分搜索

参考

💬 文章评论

二分查找 ​

1. 核心思想 ​

1.1 循环不变量 ​

2. 三种区间写法 ​

2.1 左闭右闭 [L, R] ​

2.2 左闭右开 [L, R) ​

2.3 推荐写法 ​

3. 经典变体 ​

3.1 查找左边界（第一个等于 target 的位置） ​

3.2 查找右边界（最后一个等于 target 的位置） ​

3.3 查找插入位置 ​

3.4 旋转排序数组搜索 ​

3.5 寻找峰值 ​

4. 二分答案 ​

4.1 模板 ​

4.2 经典问题 ​

4.3 示例：爱吃香蕉的 Koko ​

4.4 浮点数二分 ​

4.5 三分查找——搜索单峰函数的最值 ​

5. 边界条件速查表 ​

6. 常见错误 ​

7. 工程中的二分思想 ​

7.1 详解：B+Tree 页内二分搜索 ​

参考 ​

💬 文章评论

二分查找

1. 核心思想

1.1 循环不变量

2. 三种区间写法

2.1 左闭右闭 `[L, R]`

2.2 左闭右开 `[L, R)`

2.3 推荐写法

3. 经典变体

3.1 查找左边界（第一个等于 target 的位置）

3.2 查找右边界（最后一个等于 target 的位置）

3.3 查找插入位置

3.4 旋转排序数组搜索

3.5 寻找峰值

4. 二分答案

4.1 模板

4.2 经典问题

4.3 示例：爱吃香蕉的 Koko

4.4 浮点数二分

4.5 三分查找——搜索单峰函数的最值

5. 边界条件速查表

6. 常见错误

7. 工程中的二分思想

7.1 详解：B+Tree 页内二分搜索

参考