binary search in python


  • 2

    The idea is that for every house, you want to find the closest 2 heaters, and whichever in the 2 that is closer should warm this house. Iterate through the houses, use binary search to find the closest 2 heaters, update answer.

    class Solution(object):
        def findRadius(self, houses, heaters):
            
            heaters.sort()
            
            ans = 0
            
            for h in houses:
                hi = bisect.bisect_left(heaters, h)
                left = heaters[hi-1] if hi-1 >= 0 else float('-inf')
                right = heaters[hi] if hi < len(heaters) else float('inf')
                ans = max(ans, min(h-left, right-h))
                
            return ans
    

Log in to reply
 

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