Python binary search with a short explanation

  • 0

    I found some of the earlier posters with excellent code, however, the explanation is too long and hard to understand.

    Here is mine:

    The problem calls for a optimal value ( a ceiling) for the sum of subarray while an array is split into M subarrays. Intuitively, we know the best possible ceiling is the max element of the all input numbers (denote this as "left". Proof: if the ceiling is smaller than largest element, you can't put it in any group), and worst ceiling is the sum of all numbers (denote this as "right"). However, the left is only "possible" best solution, more than often it is too small to for me divide the array. So, I gradually increase left until I find a valid ceiling. On the other hand, the right is an valid ceiling since the number is so large that I can do whatever split I want. But it might not be the optimal answer. So, I will gradually decrease the right and try to find a better answer until it turns invalid.
    Going at both directions:
    From left: invalid -> invalid->.........
    From right: ...<- valid <- valid
    The solution turn out to be the point the two side meet! A perfect problem to be solved by binary search.

    To help out finding if a ceiling is valid, we need a utility method (isValidCeiling). It actually tries to split the array into M subarrays with a given ceiling. If possible, returns True, otherwise returns False.

    class Solution(object):
        def splitArray(self, nums, m):
            :type nums: List[int]
            :type m: int
            :rtype: int
            # A ceiling is max sum allowed for earch segment (subarray).
            def isValidCeiling(nums, m, ceiling):
                count, total = 1, 0  # count - # of segments. total - temp sum of the current segment.
                for i in range(len(nums)):
                    if total + nums[i] <= ceiling:
                        total += nums[i]  # add the number to the current segment.
                        total = nums[i]    # over the ceiling, start a new segment.
                        count += 1
                    if (count > m):
                        return False # if need more segments than m, the this an invalid ceiling.
                return True # if count <= m, then this is a valid ceiling, i.e. if we can split into less than M segments, sure enough we can split into M segments.
            l, r = max(nums), sum(nums)
            while l <= r:
                mid = (l + r) // 2
                if isValidCeiling(nums, m, mid):
                    r = mid - 1
                    l = mid + 1
            return l

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.