Write your own BS algorithm if you're asked to in an interview


  • 0

    It can happen that interviewer ask you to write your own binary search algorithm instead of letting you use the library modules. The following BS implementation is simple and concise.

        def findRadius(self, houses, heaters):
            heaters.sort()
            res = 0
    
            def _find_min_abs(value, array):
                low, high = 0, len(array) - 1
                if low == high: return abs(value - array[low])
                while low + 1 != high:
                    mid = (low + high) / 2
                    if array[mid] > value:
                        high = mid
                    elif array[mid] < value:
                        low = mid
                    else:
                        return 0
                return min(abs(value - array[low]), abs(value - array[high]))
    
            for house in houses:
                res = max(res, _find_min_abs(house, heaters))
            return res
    

Log in to reply
 

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