Linear search and binary search
Searching means finding where a value sits in a collection, or learning that it isn't there. The simplest method, linear search, looks at the elements one by one from the start. In an array of n elements that can take n comparisons, so it is O(n). It works on any array, sorted or not.
When the array is sorted, you can do much better. Look at the middle element. If it equals the value, you are done. If it is smaller than the value, then the value can only be in the right half, because everything to its left is even smaller. If it is larger, the value can only be in the left half. Either way, one comparison throws away half of the remaining elements. Repeating this is binary search, and it needs about log₂ n comparisons: roughly 10 for an array of a thousand elements, and about 20 for a million. The time is O(log n) and the extra space is O(1).
The one requirement is that the array is sorted in ascending order. On an unsorted array, discarding half the elements is not justified, and the result is meaningless.
The task
The method find receives a sorted array nums and a value. It returns the index of value, or -1 when it is not in the array. For nums = [1, 2, 4, 5] and value = 4 the result is 2, since nums[2] is 4.
Step by step
- Mark the search range.
leftandrightstart at the first and last indices,0andnums.count - 1. Both arevarbecause the loop moves them, and both bounds are inclusive:rightpoints at the last element itself. - Loop while the range isn't empty.
while left <= rightkeeps going as long as at least one candidate remains. With<instead, a range of exactly one element would never be checked. - Find the middle.
let middle = left + (right - left) / 2. Integer division truncates, so no rounding call is needed. - Match. If
nums[middle] == value, returnmiddle. - Too small. If
nums[middle] < value, the target is to the right, so setleft = middle + 1. The+ 1matters:middlehas been ruled out, and keeping it could make the loop run forever. - Too big. Otherwise set
right = middle - 1, for the same reason. - Give up. After the loop the range is empty, so return -1.
The solution in Swift
class Solution {
func find(_ nums: [Int], _ value: Int) -> Int {
var left = 0, right = nums.count - 1
while left <= right {
let 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
}
}
Swift details worth a closer look:
- Declaring two variables at once.
var left = 0, right = nums.count - 1declares twoIntvariables on one line. - Empty arrays are safe. For
[],rightis -1, soleft <= rightis false at once and the method returns -1. Nothing is indexed. - Why
left + (right - left) / 2. It gives the same index as(left + right) / 2. The sumleft + rightcan overflow in fixed-size integers, and in Swift an overflow stops the program rather than wrapping around. With a 64-bitIntand real array sizes that can't happen, but the subtraction form is safe by construction and worth keeping as a habit. - Index type. Swift arrays are indexed with
Int, not an unsigned type, sorightbeing -1 for an empty array is fine.
Tracing the example
With nums = [1, 2, 4, 5] and value = 4: left = 0, 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 method returns 2. Searching for 3 in the same array ends with left = 3 and right = 2, the loop condition fails, and the method returns -1.
Common mistakes
- Searching an unsorted array. The comparison with the middle only makes sense on sorted data.
- Off-by-one bounds. Setting
left = middleorright = middlecan leave the range unchanged and loop forever. Always move pastmiddle. - Using
<in the loop condition when the bounds are inclusive. The last remaining element is skipped, so[7]with value 7 would return -1. - Starting
rightatnums.count. That index is one past the end, and readingnums[nums.count]crashes at run time. - Duplicates. The method returns the index of some matching element, not necessarily the first or the last.
Key takeaways
- Binary search needs a sorted array and runs in
O(log n)time withO(1)extra space. - Keep an inclusive range
left...rightand halve it each time by comparing withnums[middle]. - Move the bound to
middle + 1ormiddle - 1, never tomiddleitself. - Return -1 only after the loop, when the range is empty.
Testing
[1, 2, 4, 5], value 4 gives 2.[1, 2, 4, 5], value 3 gives -1.[1, 2, 4, 5], value 1 gives 0, and value 5 gives 3.[7], value 7 gives 0.[], value 3 gives -1.
