二分搜索问题中，如何确定返回左指针还是右指针？

先结合你在LeetCode 875题中的代码，分析问题根源，再总结通用规则：

一、你的代码逻辑拆解 #

我们的目标是找最小的k，使得吃完所有香蕉的时间≤h。你的二分逻辑如下：

• 搜索区间：[1, max(piles)]，lp是左边界，rp是右边界
• 每次取中间值speed，计算所需时间hours：
  • 如果hours > h：当前speed太慢，不满足条件，需要往更大的方向找，所以lp = speed + 1
  • 如果hours ≤ h：当前speed满足条件，但可能存在更小的符合条件的k，所以rp = speed - 1

当循环while lp <= rp结束时，必然是lp > rp。此时：

• lp指向第一个满足条件的k（也就是我们要找的最小k）
• rp指向最后一个不满足条件的k

这就是为什么返回lp通过测试，返回rp失败——因为rp对应的是不符合要求的速度。

二、通用判断方法 #

不需要试错，只要明确两个核心点，就能确定返回哪个指针：

1. 先明确搜索目标 #

你要找的是：

• 第一个满足条件的元素（比如本题的最小k）
• 还是最后一个满足条件的元素（比如反过来，找最大的k使得吃香蕉时间≥h）

2. 对应指针移动规则与返回值 #

假设我们定义f(x)为判断x是否满足条件的函数：

3. 验证示例（以本题为例） #

• f(x)：吃完香蕉的时间≤h
• 目标：第一个满足f(x)的元素（最小k）
• 操作：f(mid)为真时rp=mid-1，为假时lp=mid+1
• 返回lp，完全符合规则

三、模拟指针变化（帮助理解） #

以示例piles=[3,6,7,11], h=8为例：

1. 初始lp=1, rp=11，mid=6，计算得hours=6≤8，rp=5
2. lp=1, rp=5，mid=3，计算得hours=10>8，lp=4
3. lp=4, rp=5，mid=4，计算得hours=8≤8，rp=3
4. 此时lp=4>rp=3，循环结束，lp=4就是最小符合条件的k

内容的提问来源于stack exchange，提问作者Jensen Jacob