二分查找进阶 - 两段性的本质

引言

在二分查找基础文章中，我们学习了如何在有序数组上应用二分查找。但如果我告诉你，二分查找也能在无序数组上工作呢？

很多人认为二分查找必须在有序数组上进行。这是一个误解。真正的要求是更本质的东西。

❌ 错误理解：二分查找只能用于有序数组
✅ 正确理解：能划分成两段就能用二分

这个洞察打开了一个全新的问题世界，都可以用二分查找来解决！

两段性的本质

什么是两段性？

对于搜索空间中的任意位置 i，如果我们能定义一个条件 f(i)，使得：

f(0), f(1), ..., f(k-1) = FALSE
f(k), f(k+1), ..., f(n-1) = TRUE

那么搜索空间就具有两段性，我们可以用二分查找来找到 k。

可视化理解

传统有序数组：
索引:   0   1   2   3   4   5   6   7   8
值:     1   3   5   7   9  11  13  15  17
        ←─── < 9 ───→  ←───── >= 9 ─────→
        
旋转排序数组：
索引:   0   1   2   3   4   5   6   7
值:     4   5   6   7   0   1   2   3
        ←─ >= nums[0] ─→ ←─ < nums[0] ─→
        
寻找峰值：
索引:   0   1   2   3   4   5   6
值:     1   3   5   7   4   2   1
        ←── 上升段 ──→  ←─ 下降段 ─→

三种情况都具有两段性，所以二分查找都适用！

关键原则

💡 找到正确的条件：一旦确定了将搜索空间划分为两段的条件，二分查找模板就可以直接套用。

题目一：搜索旋转排序数组 (LC 33)

题目

在一个原本有序但在某个位置旋转过的数组中搜索目标值。

输入:  nums = [4,5,6,7,0,1,2], target = 0
输出: 4

输入:  nums = [4,5,6,7,0,1,2], target = 3
输出: -1

关键洞察

虽然数组整体不有序，但它具有两段性：

数组: [4, 5, 6, 7, 0, 1, 2]
      ←── >= 4 ──→ ←─ < 4 ─→
        
在任意时刻，至少有一半是有序的！
- 如果 nums[left] <= nums[mid]: 左半部分有序
- 否则: 右半部分有序

逐步示例

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

第1步: left=0, right=6, mid=3
       nums[mid] = 7
       nums[left]=4 <= nums[mid]=7 → 左半 [4,5,6,7] 有序
       0 在 [4,7) 区间内吗？否 → 搜索右半
       left = 4

第2步: left=4, right=6, mid=5
       nums[mid] = 1
       nums[left]=0 <= nums[mid]=1 → 左半 [0,1] 有序
       0 在 [0,1) 区间内吗？是！→ 搜索左半
       right = 4

第3步: left=4, right=4, mid=4
       nums[mid] = 0 == target ✓
       返回 4

解法

复杂度

• 时间: O(log n)
• 空间: O(1)

题目二：寻找旋转排序数组中的最小值 (LC 153)

题目

找出旋转排序数组中的最小元素。

输入:  nums = [3,4,5,1,2]
输出: 1

输入:  nums = [4,5,6,7,0,1,2]
输出: 0

关键洞察

两段性非常清晰：

数组: [4, 5, 6, 7, 0, 1, 2]
      ←── > right ──→ ←── <= right ──→
                      ↑
                   最小值

条件: nums[mid] > nums[right]
- TRUE: 最小值在右半部分
- FALSE: 最小值在左半部分（包括 mid）

解法

为什么要和 right 比较？

和 nums[left] 比较对于未旋转数组不起作用：

未旋转: [1, 2, 3, 4, 5]
nums[mid]=3 >= nums[left]=1  → 会向右走，但最小值在左边！

和 right 比较:
nums[mid]=3 <= nums[right]=5 → 正确地向左走 ✓

题目三：寻找峰值 (LC 162)

题目

找出满足 nums[i] > nums[i-1] 且 nums[i] > nums[i+1] 的峰值元素。假设 nums[-1] = nums[n] = -∞。

输入:  nums = [1,2,3,1]
输出: 2 (峰值 3 的索引)

输入:  nums = [1,2,1,3,5,6,4]
输出: 5 (或 1，两个都有效)

关键洞察

数组可以是无序的，但仍然具有两段性：

数组: [1, 2, 1, 3, 5, 6, 4]
                       ↑ 峰值
                        
在每个 mid，与 mid+1 比较：
- nums[mid] > nums[mid+1]: 下降坡 → 峰值在左侧（包括 mid）
- nums[mid] < nums[mid+1]: 上升坡 → 峰值在右侧

这保证我们能找到「一个」峰值（不一定是最高的）。

可视化证明

为什么这总能找到峰值？

情况 1: mid 处于上升坡
    nums[mid] < nums[mid+1]
    
        ?
       /
      mid
      
    我们向右走。由于 nums[n] = -∞，在到达边界之前
    必然会遇到峰值。

情况 2: mid 处于下降坡
    nums[mid] > nums[mid+1]
    
    mid
      \
       ?
       
    我们向左走（包括 mid）。由于 nums[-1] = -∞，
    在到达边界之前必然会遇到峰值。

解法

复杂度

• 时间: O(log n)
• 空间: O(1)

题目四：有序矩阵中第 K 小的元素 (LC 378)

题目

在一个 n×n 矩阵中找第 k 小的元素，矩阵每行每列都是有序的。

矩阵:
[1,  5,  9]
[10, 11, 13]
[12, 13, 15]

k = 8
输出: 13 (第 8 小的元素)

关键洞察

这是在值空间上二分，而不是索引空间！

值范围: [matrix[0][0], matrix[n-1][n-1]] = [1, 15]

对于任意值 mid：
- 统计 <= mid 的元素个数
- 如果 count < k: 答案 > mid
- 如果 count >= k: 答案 <= mid

这是在「值空间」上的两段性！

高效计数方法

使用从左下角开始的阶梯法：

目标 = 11

[1,  5,  9]      起点: row=2, col=0
[10, 11, 13]     
[12, 13, 15]     12 > 11, 向上走
 ↑
 
[1,  5,  9]      10 <= 11, count += 2, 向右走
[10, 11, 13]     
 →
 
[1,  5,  9]      11 <= 11, count += 2, 向右走
    [10, 11, 13]     
         →
         
[1,  5,  9]      13 > 11, 向上走
    [10, 11, 13]     
             ↑
             
[1,  5,  9]      9 <= 11, count += 1, 向右走
         →
         
越界。总计 count = 5

解法

复杂度

• 时间: O(n × log(max - min))
• 空间: O(1)

答案空间上的二分

一个强大的模式：当题目要求找到满足某个条件的最小/最大值时，在答案空间上二分！

模式识别

寻找这些关键词：

• “找到最小的 X 使得…”
• “找到最大的 Y 能够…”
• “最小/最大的值是多少…”

通用模板

function findOptimalAnswer(problem) {
  let left = minPossibleAnswer;
  let right = maxPossibleAnswer;
  
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    
    if (canAchieve(problem, mid)) {
      // 找到一个有效答案，尝试找更优的
      right = mid;  // 找最小值
      // left = mid + 1;  // 找最大值（需要修改）
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

题目五：爱吃香蕉的珂珂 (LC 875)

题目

珂珂每小时可以吃 k 根香蕉。给定香蕉堆和 h 小时时间，找出能吃完所有香蕉的最小 k。

输入:  piles = [3,6,7,11], h = 8
输出: 4

解释: 
k=4 时: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 小时 ✓

关键洞察

在吃香蕉速度（答案空间）上二分：

速度范围: [1, max(piles)]

对于任意速度 k：
- 计算需要的小时数
- 如果 hours <= h: 速度足够，尝试更慢
- 如果 hours > h: 速度太慢，需要更快

两段性：
[1, 2, ..., k-1] = 太慢 (hours > h)
[k, k+1, ..., max] = 足够快 (hours <= h)

解法

复杂度

• 时间: O(n × log(max(piles)))
• 空间: O(1)

题目六：在 D 天内送达包裹的能力 (LC 1011)

题目

找出能在 D 天内送达所有包裹的最小船载重量。

输入:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出: 15

解释:
第1天: 1,2,3,4,5 (sum=15)
第2天: 6,7 (sum=13)
第3天: 8 (sum=8)
第4天: 9 (sum=9)
第5天: 10 (sum=10)

关键洞察

在船的容量上二分：

容量范围: [max(weights), sum(weights)]
- 最小值：必须装下最大的单个包裹
- 最大值：一天运完所有包裹

对于任意容量 c：
- 计算需要的天数
- 如果 days <= D: 容量足够，尝试更小
- 如果 days > D: 容量太小，需要更大

解法

复杂度

• 时间: O(n × log(sum - max))
• 空间: O(1)

模式识别指南

什么时候使用两段性二分

提示二分查找的信号

1. 有序或部分有序数据
2. 最小/最大优化问题
3. “至少”或”至多”约束
4. 答案可以在 O(n) 或更短时间内验证

模板总结

// 类型 1: 在修改过的有序数组中搜索
while (left <= right) {
  const mid = ...;
  if (found) return mid;
  // 根据两段性确定搜索哪一半
}

// 类型 2: 找分界点（满足条件的最小值）
while (left < right) {
  const mid = ...;
  if (condition(mid)) {
    right = mid;  // 找到有效值，尝试更小
  } else {
    left = mid + 1;  // 无效，需要更大
  }
}
return left;

// 类型 3: 找分界点（满足条件的最大值）
while (left < right) {
  const mid = left + Math.floor((right - left + 1) / 2);  // 注意: +1
  if (condition(mid)) {
    left = mid;  // 找到有效值，尝试更大
  } else {
    right = mid - 1;  // 无效，需要更小
  }
}
return left;

总结

🎯 关键要点

1. 两段性是本质：只要能把搜索空间划分成两个不同的区域，二分查找就适用

2. 不只适用于有序数组：旋转数组、峰值查找、答案空间问题都可以用二分

3. 答案空间上的二分：当寻找最优值时，在答案范围内二分，配合验证函数

4. 模式识别：

   • 修改过的有序数组 → 与边界比较
   • 找满足 X 的最小值 → while (l < r), right = mid
   • 找满足 X 的最大值 → while (l < r), left = mid

📊 问题分类

💡 面试技巧

1. 写代码前先确定两段性条件
2. 清晰定义分隔两段的条件
3. 根据找最小值还是最大值选择正确的模板
4. 用边界情况验证：空数组、单元素、全相同元素

🎯 通过理解本质来掌握二分查找：关键不是有序性，而是能否划分成两段！

📚 相关文章

• 二分查找基础 - 掌握基本模板