Binary Search
EasyThe problem
Given a list of numbers sorted from smallest to biggest, and a target, return the position (index) of the target in the list. If the target is not in the list, return -1.
- Example 1Input: nums = [2, 4, 6, 8, 10], target = 8Output: 3
nums[3] is 8.
- Example 2Input: nums = [2, 4, 6, 8, 10], target = 5Output: -1
5 is not in the list.
Limits
- 1 ≤ nums.length ≤ 100,000
- All numbers in nums are different
- nums is sorted in increasing order
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Look at the middle element. What does it tell you about which half to keep?
The idea
lo=0, hi=n−1; mid; if equal return, if too small lo=mid+1, else hi=mid−1.
Target: O(log n) time, O(1) space
Go function shape
func search(nums []int, target int) intReference solution
Tested with go test. Try it yourself first, then compare.
// Search: index of target in a sorted slice, or -1.
// Find the first index whose value is >= target, then check it really is target.
func Search(nums []int, target int) int {
lo, hi := 0, len(nums)
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] >= target {
hi = mid
} else {
lo = mid + 1
}
}
if lo < len(nums) && nums[lo] == target {
return lo
}
return -1
}