You are hunting for a friend's number in a paper phone book of a million names. Would you start at "Aardvark" and read every single entry until you reach "Zara"? Of course not — you flip to the middle, see whether you have gone too far, and throw away half the book in one move. That instinct is the difference between the two great search algorithms: linear search (check every item) and binary search (repeatedly halve a sorted list).
Why this matters: Searching is one of the most common jobs a computer does — finding a contact, a file, a product, a record. Choosing the right search can be the difference between an answer that is instant and one that keeps a user waiting.
Binary search: each step throws away half of what is left.
Linear search — one at a time
Linear search inspects items one by one from the start.
Linear search starts at the first item and checks each in turn until it finds the target or reaches the end. It is simple, and crucially it works on any list — sorted or not. The catch: in the worst case (the item is last, or missing) it must look at every element.
Binary search — halve and conquer
Binary search is far faster but demands one thing: the list must be sorted first. It looks at the middle item, then:
if that is the target — done;
if the target is smaller, throw away the right half and repeat on the left;
if the target is bigger, throw away the left half and repeat on the right.
Because each step discards half, a list of a million items is found in about 20 checks, not a million.
Linear search
Binary search
List must be sorted?
No
Yes
Worst-case checks (n items)
n
about log₂n
Speed on large lists
Slow
Very fast
Simplicity
Very simple
A little trickier
Worked reasoning: Find 13 in [2, 5, 8, 11, 13, 21, 30, 44] (8 items). Middle of positions 1–8 is position 4 = 11. 13 > 11, so search positions 5–8. New middle is position 6 = 21. 13 < 21, so search position 5. That value is 13 — found in just 3 checks. A linear search would have taken 5.
Common mistake: Running binary search on an unsorted list.
On an unsorted list binary search can throw away the target itself.
It will happily throw away the half that actually contains your item and report "not found". Always sort first — or use linear search.
Memory hook:Linear = Look at every Line. Binary = Break in half. And binary needs a tidy (sorted) room to work in.