二分查找问题中如何知道返回左指针还是右指针？

Question

我正在解决LeetCode问题875。科科吃香蕉:

科科喜欢吃香蕉。有

n

堆香蕉，第

i

^第堆有

piles[i]

香蕉。警卫已经走了，

h

小时后就会回来。

Koko 可以决定她每小时吃香蕉的速度

k

。每个小时，她都会选择一些香蕉并吃掉那堆中的

k

香蕉。如果这堆香蕉少于

k

，她会吃掉所有香蕉，并且在这一小时内不会再吃更多香蕉。

科科喜欢慢慢吃，但仍然想在守卫回来之前吃完所有香蕉。

返回 最小整数

k

这样她就能在

h

小时内吃完所有香蕉。

示例1：

• 输入：

  piles = [3,6,7,11], h = 8

• 输出：

  4

这是我的代码：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lp=1
        rp=max(piles)
        while lp<=rp:
            speed=(lp+rp)//2
            hours=0
            for pile in piles:
                hours+=ceil(pile/speed)
            if hours>h:
                lp=speed+1
            else:
                rp=speed-1
        return lp

问题

当我在这里返回正确的指针时，测试用例失败了。但是，当我使用左指针时，它就通过了。

问题

对于二分查找问题，有没有通用的方法可以知道是返回左指针还是右指针？

我只是在这里进行了尝试和错误。我想知道为什么会这样，不仅仅是针对这个问题，而是针对一般的二分搜索问题。

Answer 1

二分搜索实现有两个问题：

• rp=speed-1

  应该是

  rp=speed

  ，因为

  speed

  仍然是一个潜在的解决方案，不应被排除。

• while lp<=rp

  应该是

  while lp<rp

  ，因为

  lp

  和

  rp

  都是潜在的解，所以如果它们相等，则只剩下一个解，不应该进行进一步的迭代。有了上面的第一个更改，就需要进行此更改，否则会出现无限循环。

不是问题，而是避免转换为浮点并执行

ceil(pile/speed)

，而不是 

(pile + speed - 1) // speed