Binary Search Solution in Go (beats 94%)


  • 0
    S
    import (
        "math" 
        "sort"
    )
    func findRadius(houses []int, heaters []int) int {
        sort.Ints(heaters)
        res := -math.MaxInt32
        var dist1, dist2, index int
        for _, house := range houses {
            index = binarySearch(house, heaters)
            if index < 0 {
                index = -(index+1)
            }
            
            dist1 = math.MaxInt32
            if index - 1 >= 0 {
                dist1 = house - heaters[index-1]
            }
            dist2 = math.MaxInt32
            if index < len(heaters) {
                dist2 = heaters[index] - house
            }
            
            res = Max(res, Min(dist1, dist2)) 
        }
        return res
    }
    
    func Min(i int, j int) int {
        if i <= j {
            return i
        }
        return j
    }
    
    func Max(i int, j int) int {
        if i >= j {
            return i
        }
        return j
    }
    
    func binarySearch(num int, nums []int) int {
        l, r := 0, len(nums)-1
        var mid int
        for l <= r {
            mid = (l + r)/2
            if nums[mid] == num {
                return mid
            } else if nums[mid] > num{
                r = mid - 1
            } else {
                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.