使用二进制搜索时如何决定使用中低或中高？

Question

最近在玩二分查找算法。我更喜欢以 while lo < hi.

开头的经典模板

今天遇到一个问题，比较迷茫。 leetcode题目是给定一个整数数组ribbons，其中ribbons[i]代表第i条ribbon的长度，和一个整数k。您可以将任何色带切割成任意数量的正整数长度段，或者根本不进行切割。目标是获得 k 个所有相同正整数长度的色带。您可以丢弃剪裁后多余的丝带。 Return你能得到k条带的最大可能正整数长度，如果不能得到k条相同长度的条带则为0。示例输入和输出是：

Input: ribbons = [7,5,9], k = 4
Output: 4

这段代码可以return想要的结果，而且它使用的是higher mid:

class Solution(object):
    def maxLength(self, ribbons, k):
        s = sum(ribbons)
        if s//k == 0:
            return 0
        lo, hi = 1, s//k
        def bs(cut):
            return sum([r//cut for r in ribbons]) >= k

        while lo < hi:
            mid = (lo+hi+1)//2
            if bs(mid):
                lo = mid
            else:
                hi = mid-1
        return lo

这段代码也能给出正确答案，但使用的是lower mid:

class Solution(object):

    def maxLength(self, ribbons, k):
        s = sum(ribbons)
        if s < k: return 0

        def bs(cut):
            return sum([r // cut for r in ribbons]) >= k
        lo, hi = 1, s//k
        while lo <= hi:
            mid = (lo+hi) // 2
            if bs(mid):
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

我的问题是，如何决定何时使用较高或较低的中值？在什么情况下 lo 或 hi 应该被 returned？这真的让我很困惑。感谢任何帮助。

Answer 1

你的一个实现被破坏了:)

最终，选择向下或向上舍入 mid 取决于您的支票是过低还是过高。

在你的例子中，bs(mid) 是一个过高的支票，所以你的 if 应该是这样的：

if bs(mid):
    # not too high (correct answer is >=)
    lo = mid
else
    # too high (correct answer is <)
    hi = mid-1

因为你的支票太高了，可能的下一个边界是mid和mid-1。如果你的支票太低，那么可能性是 mid+1 和 mid.

为了保证范围在每次迭代中都变小（避免无限循环）并且总是lo <= hi，你需要lo <= mid-1 < mid <= hi。鉴于 lo < hi，这是由 mid = lo + (hi-lo+1)//2 保证的——四舍五入。

如果您的支票太低，那么您会要求 lo <= mid < mid+1 <= hi。使用 lo < hi，由 mid = lo + (hi-lo)//2.

保证

使用二进制搜索时如何决定使用中低或中高？

how to decide to use lower mid or higher mid when using binary search?

algorithm

search

binary-search