Searching: linear against binary
To find a value in a slice you can look at the elements one by one from the start. That is a linear search, and in the worst case it checks every element: O(n) time. It works on any slice, sorted or not.
If the slice is sorted, you can do much better. Look at the middle element. If it is the value you want, you are done. If it is smaller than the value, the value can only be in the right half, because everything to the left of the middle is smaller still. If it is larger, the value can only be in the left half. Either way, half of the remaining elements are discarded with one comparison. Repeating this is binary search, and it takes O(log n) time: a sorted slice of a million elements needs at most about 20 comparisons.
The price is the precondition. Binary search on an unsorted slice gives wrong answers, so it only makes sense when the data is already sorted or is worth sorting first.
The exercise
The function find receives a sorted slice of integers, nums, and a value. It returns the index of value in nums, or -1 when it isn't there. With nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4. The budget is O(log n) time and O(1) extra space, so the search must be a loop that keeps only a few integers, not a recursion that copies slices.
Step by step
- Keep two markers.
leftis the first index still possible andrightis the last one. Both are inclusive:rightstarts atlen(nums)-1, the last valid index. A single:=declares both. - Loop while the range has elements. Go has no
while; aforwith only a condition does the job. The condition isleft <= right, with<=because when the two are equal there is still one element to check. - Find the middle.
left + (right-left)/2is the index halfway between them. Dividing twoints in Go truncates, so no rounding function is needed. - Found it: if
nums[middle]equalsvalue, returnmiddle. - Middle too small: the value can only be to the right, so set
left = middle + 1. The+ 1matters becausemiddleitself has been ruled out. - Middle too large: set
right = middle - 1, for the same reason. - Not found: if the loop ends, the range is empty and every candidate was ruled out, so return
-1after the loop.
The solution in Go
func find(nums []int, value int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)/2
if nums[middle] == value {
return middle
} else if nums[middle] < value {
left = middle + 1
} else {
right = middle - 1
}
}
return -1
}
Here is a trace for nums = [1, 2, 4, 5] and value = 4. At the start left = 0 and right = 3, so middle = 1 and nums[1] is 2. That is smaller than 4, so left becomes 2. Now middle = 2 + (3-2)/2 = 2 and nums[2] is 4, so the function returns 2.
For value = 3 in the same slice, the first step is identical (left becomes 2). Then nums[2] = 4 is larger than 3, so right becomes 1. Now left > right, the loop ends, and the function returns -1.
Go details
- Multiple assignment.
left, right := 0, len(nums)-1declares two variables in one statement. foris the only loop.for left <= right { ... }is Go's while loop.- Integer division truncates toward zero. Here the numerator is never negative, so it is the same as rounding down.
- Why
left + (right-left)/2. It gives the same index as(left + right) / 2but never adds the two indices. In languages with 32-bit integers that sum can overflow for huge arrays; Go'sintis 64 bits on 64-bit machines, so it isn't a risk in practice here. It is still the form to remember. - Slices are not copied. The function passes the slice header (pointer, length, capacity) and works on the same elements, so it uses constant extra space.
- The empty slice. With
len(nums) == 0,rightis -1, the condition is false at once and the function returns -1. No element is read.
Common mistakes
- Using
left < right. The loop then skips a range of one element. Withnums = [7]andvalue = 7the function would return -1. - Setting
left = middleorright = middle. When the range is two elements,middleequalsleft, soleft = middlechanges nothing and the loop never ends. - Using the search on an unsorted slice. The halving logic assumes order, so the result is meaningless otherwise.
- Returning
0for a miss. Index 0 is a valid position, so the not-found signal must be -1. - Returning the value instead of the index. The function returns
middle, notnums[middle].
Key takeaways
- Binary search needs a sorted slice and runs in
O(log n)time withO(1)extra space. - Keep an inclusive range
[left, right]and shrink it pastmiddle, never onto it. - Loop while
left <= right; when the loop ends the value is absent. - This same loop is the base for variations such as lower bound, which searches for a position instead of an exact match.