Linear & binary search

The baseline

Linear search checks every item until it finds a match

Linear search is what you would do by hand with an unsorted pile: start at the first item and compare each one with the target until you find it or run out. It needs nothing from the list, so it works on anything.

It finds a match at the front in one step, but a missing value, or one at the end, costs n comparisons: O(n) in the worst case. When you search an unsorted list once, nothing does better, because any item you skip might be the one you want.

The idea

In a sorted list, one comparison rules out half the items

A list is sorted when every item is no larger than the one after it. That order is information: compare the target with the middle item, and you know which half it must be in. If the middle item is smaller than the target, everything to its left is smaller too, and can be ruled out without being looked at.

Binary search keeps two indexes, lo and hi, around the part of the list that could still hold the target. Each step compares the middle item and moves one end past it, halving the range, until it finds the target or the range is empty.

The rule

Binary search needs a sorted list, and in return finds any item in O(log n): each comparison halves the range that could still hold it.

Halving is what Big-O notation & analysis showed with no list at all: a million items take about 20 steps, a billion about 30.

The details

Binary search is short, and easy to get subtly wrong

Three details cause most bugs:

The loop condition. With both ends included in the range, the loop runs while lo ≤ hi. Writing < skips the last one-item range and misses targets.
Moving past the middle. After ruling out the middle item, set lo ← mid + 1 or hi ← mid − 1. Setting lo ← mid can loop forever once two items are left.
Computing the middle. mid ← lo + floor((hi − lo) / 2) is the safe form. In languages with fixed-size integers, (lo + hi) / 2 can overflow when the list is huge.

The search also says something useful when the target is missing: when the loop ends, lo is where the target would go to keep the list sorted.

Duplicates

Finding the first match keeps searching after a hit

In [1, 3, 3, 3, 7, 9], a plain binary search for 3 may stop at any of the three. Often you need a specific one, such as the first: to count how many 3s there are, or to find where a range of values begins.

The fix is to keep going. Look for the first position whose value is at least the target, the lower bound. When the middle value is big enough, it might be the answer, but so might something further left, so remember it and keep searching the left half:

It still takes O(log n), and the same shape ("find the first place where a yes/no question turns to yes") solves far more than lookups. Binary search on the answer uses it to search over possible answers instead of over a list.

In practice

Sorting first pays off when you search many times

Situation	Use	Cost
Unsorted list, one search	Linear search	O(n)
Sorted list	Binary search	O(log n) per search
Unsorted list, many searches	Sort once, then binary search	O(n log n) once, then O(log n) each
Exact-match lookups only	A hash set or map	O(1) on average

Sorting costs O(n log n), as the next pages show, so it only pays when it is shared by many searches. And if all you ever ask is "is this key here?", Hash tables & maps answer in O(1). Binary search earns its place when order matters: the first item at least x, every item between two values, the nearest item to a value.

Standard libraries include it: bisect_left in Python's bisect module, Arrays.binarySearch in Java and std::lower_bound in C++.

Check yourself

4 questions

1. Binary search is run on the unsorted list [9, 2, 7, 4, 5], looking for 9. What happens?

2. About how many comparisons does binary search need in the worst case for a sorted list of 1,000,000 items?

3. A binary search uses while lo < hi with both ends inclusive. What goes wrong?

4. You need the number of 3s in a long sorted list. What is the fastest approach?

Takeaways

Remember this

Linear search works on any list and costs O(n); on an unsorted list searched once, nothing does better.
Binary search needs sorted order and costs O(log n), because each comparison halves the range.
Loop while lo ≤ hi, move past the middle (mid + 1, mid − 1) and compute mid as lo + floor((hi − lo) / 2).
A lower-bound search finds the first item at least a target, which handles duplicates and ranges.
Sort first only when many searches share the cost; for exact-match lookups, a hash set is faster still.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

3 more once you have practiced Basic sorting, Prefix sums. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.