Binary Search Python Solution with Brief Explanation


  • 0
    W

    The basic idea is:

    1. For each house, I find the left-nearest and right-nearest heaters and calculate two distances;
    2. Find the minimum of the two distances for all houses;
    3. Find the maximum of all the minimums in step2.

    Several things need to be considered very carefully:

    1. Heaters has to be sorted;
    2. Two border situation: house is larger than any element in heaters, or house is smaller than any element in heaters;
    3. Understand the return index of bisect(), and manipulate carefully.
      FYI: Link to bisect(): disect()
    class Solution(object):
        def findRadius(self, houses, heaters):
            import bisect
            heaters.sort()
            rs = 0
            for i in houses:
                index = bisect.bisect(heaters, i)
                leftVal = 10 ** 9 if index == 0 else i-heaters[index-1]
                rightVal = 10 ** 9 if index == len(heaters) else heaters[index] - i
                rs = max(rs, min(leftVal, rightVal))
            return rs
    

Log in to reply
 

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