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

user_16784184 0
Viewed 94

recently I am playing with binary search algorithm. I prefer the classic template starting with while lo < hi.

This day i met a question, which makes me more confused. The leetcode problem is that given an integer array ribbons, where ribbons[i] represents the length of the i-th ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all. The goal is to obtain k ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting. Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length. The example input and output is :

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

This code can return the desired result, and it is using 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

This code can also give the right answer, but use 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

My question is, how to decide when to use higher or lower mid? In what case should the lo or hi be returned? This really confuses me. Any help is appreciated.

binary-search search algorithm
1 Answers

One of your implementations is broken :)

Ultimately, the choice of rounding mid down or up depends on whether you have a too-low check or a too-high check.

In your case, bs(mid) is a too-high check, so your if should look like this:

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

Because you have a too-high check, the possible next next boundaries are mid and mid-1. If you had a too-low check, then the possibilities would be mid+1 and mid.

In order to guarantee the the range gets smaller in every iteration (avoids infinite loop) and that lo <= hi always, you require that lo <= mid-1 < mid <= hi. Given that lo < hi, this is guaranteed by mid = lo + (hi-lo+1)//2 -- round up.

If you had a too-low check, then you'd require that lo <= mid < mid+1 <= hi. With lo < hi, that is guaranteed by mid = lo + (hi-lo)//2.

user_54835260
Related