Searching a sorted array
One comparison with the middle element rules out half the array. Watch it happen on a hit and on a miss, and see where the search stops when the value is absent.
What one comparison buys
A linear scan learns one thing from each comparison: the element it looked at is not the target. In a sorted
array a comparison with the middle element learns far more. If a[mid] is smaller than the target,
every element to its left is smaller still, so half the array is ruled out at once. If it is larger, the right
half goes.
The search keeps a range [lo, hi] that must contain the target if it is anywhere, compares with
the middle of that range, and throws away the half that cannot contain it.
A search that finds the value
The exact-match template from the first module, on a sorted array of nine values.
Looking for 42.
-
Step 1 / 3lo0hi8
Looking for 42. If it is anywhere, it is in [lo, hi] = [0, 8]: the whole array.
-
Step 2 / 3lo0mid4hi8a[mid]27
a[4] = 27 < 42. Everything from index 0 to 4 is at most 27, so none of it can be 42: lo = 5.
-
Step 3 / 3lo5mid6hi8
a[6] = 42, the target. Return 6.
comparedruled outfound
A search that does not
When the target is absent the range shrinks until it is empty. Nothing is returned early, and the place
where lo stops is worth noticing: it is the index the target would occupy if it were inserted.
The next module builds on exactly that.
Looking for 24, which is not in the array.
-
Step 1 / 6lo0hi8
Looking for 24. If it is anywhere, it is in [lo, hi] = [0, 8]: the whole array.
-
Step 2 / 6lo0mid4hi8a[mid]27
a[4] = 27 > 24. Everything from index 4 to 8 is at least 27: hi = 3.
-
Step 3 / 6lo0mid1hi3a[mid]8
a[1] = 8 < 24. Everything from index 0 to 1 is at most 8, so none of it can be 24: lo = 2.
-
Step 4 / 6lo2mid2hi3a[mid]14
a[2] = 14 < 24. Everything from index 2 to 2 is at most 14, so none of it can be 24: lo = 3.
-
Step 5 / 6lo3mid3hi3a[mid]21
a[3] = 21 < 24. Everything from index 3 to 3 is at most 21, so none of it can be 24: lo = 4.
-
Step 6 / 6lo4hi3
lo = 4 has passed hi = 3: the range is empty, so 24 is not in the array. Return −1. Note where lo stopped: index 4 is where 24 would be inserted.
Why it takes log n steps
Each comparison at least halves the range, so after k comparisons at most n / 2k candidates remain. The search ends when none remain, after at most ⌊log₂ n⌋ + 1 comparisons.
| Array length n | Worst-case comparisons | A linear scan, worst case |
|---|---|---|
| 10 | 4 | 10 |
| 1,000 | 10 | 1,000 |
| 1,000,000 | 20 | 1,000,000 |
| 1,000,000,000 | 30 | 1,000,000,000 |
The array must already be sorted. Sorting first costs O(n log n), so for a single lookup in unsorted data a scan is cheaper; binary search pays off when the same sorted data is searched many times.
The code
The reference solution to the first problem in this module. Note the loop condition lo ≤ hi,
which keeps the loop running while one candidate is left, and the two updates that both step past
mid.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # if target is anywhere, it is in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # nums[lo..mid] are all too small
else:
hi = mid - 1 # nums[mid..hi] are all too large
return -1#include <vector>
int solve(const std::vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1; // if target is anywhere, it is in nums[lo..hi]
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // no overflow
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1; // if target is anywhere, it is in nums[lo..hi]
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // no overflow
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
}function search(nums, target) {
let lo = 0, hi = nums.length - 1; // if target is anywhere, it is in nums[lo..hi]
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}fn solve(nums: &[i64], target: i64) -> i64 {
// half-open [lo, hi) keeps the indices unsigned: hi = mid never goes below zero
let (mut lo, mut hi) = (0usize, nums.len());
while lo < hi {
let mid = lo + (hi - lo) / 2;
if nums[mid] == target {
return mid as i64;
}
if nums[mid] < target { lo = mid + 1 } else { hi = mid }
}
-1
}import Data.Array
solve :: [Int] -> Int -> Int
solve nums target = go 0 (n - 1)
where
n = length nums
a = listArray (0, n - 1) nums
-- if target is anywhere, it is in a[lo..hi]
go lo hi
| lo > hi = -1
| a ! mid == target = mid
| a ! mid < target = go (mid + 1) hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo) `div` 2The same code is the reference solution to Find a value in a sorted array, where it is compiled and run against the tests in all six languages.
What the libraries give you
In an interview you are usually asked to write the search. In practice, and to check your own, every language has one.
| Language | Call | What it returns |
|---|---|---|
| Python | bisect.bisect_left(a, x) | the insertion point; x is present if that index is in range and holds x |
| C++ | std::binary_search(a.begin(), a.end(), x) | true or false only; use std::lower_bound for a position |
| Java | Arrays.binarySearch(a, x) | an index of x, or −(insertion point) − 1 when absent |
| Rust | a.binary_search(&x) | Ok(index) or Err(insertion point) |
| JavaScript | none built in | write the loop |
| Haskell | none for arrays in base | write the loop, or keep the data in a Data.Set and use member |
With repeated values, Java's and Rust's calls return the index of any one match, not the first. When the first or last occurrence matters, use a bound, which is the next module.