Last active
October 17, 2022 03:13
-
-
Save trungdlp-wolffun/48948c6ded9beb121bbdf7fe621fe911 to your computer and use it in GitHub Desktop.
Golang: Find closest element in array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
func findClosest(arr []int, target int) int { | |
n := len(arr) | |
if n == 0 { | |
panic("empty array") | |
} | |
if target < arr[0] { | |
return arr[0] | |
} | |
if target > arr[n-1] { | |
return arr[n-1] | |
} | |
left, mid, right := 0, 0, n | |
for left < right { | |
mid = (left + right) / 2 | |
if arr[mid] == target { | |
return arr[mid] | |
} | |
if target < arr[mid] { | |
if mid > 0 && target > arr[mid-1] { | |
return getClosest(arr[mid-1], arr[mid], target) | |
} | |
right = mid | |
} else { | |
if mid < n-1 && target < arr[mid+1] { | |
return getClosest(arr[mid], arr[mid+1], target) | |
} | |
left = mid + 1 | |
} | |
} | |
return arr[mid] | |
} | |
func getClosest(left, right, target int) int { | |
if target-left >= right-target { | |
return right | |
} | |
return left | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment