Skip to content
BENIBIX Learn

Linear Search vs Binary Search

Linear search checks every item, one by one, and works on any list. Binary search needs a sorted list, but halves it each step, so a million items take about 20 checks.

Development🧮 Algorithms & Data Structures

Linear Search

Checking each item in turn until you find a match.

Linear search finds an item by checking each one in turn, from the start. It stops when it finds a match, or when it reaches the end. It works on any list, sorted or not. For a list of n items it can take up to n checks, so it is O(n). It is the right choice for short lists and lists you search only once.

Example
Jack looks for 9 in the list 4, 7, 1, 9. Linear search checks four numbers and finds it at position 3.
Why it matters
It is simple and always works. Knowing its cost tells you when to reach for something faster.
Full entry
Development🧮 Algorithms & Data Structures

Binary Search

Finding an item in a sorted list. Each step cuts the search in half.

Binary search finds an item in a sorted list by cutting the search in half each step. It checks the middle item first. If the target is smaller, it throws away the right half; if bigger, the left half. A list of 1,000,000 items needs at most 20 checks, so it is O(log n). It only works when the list is already sorted.

Example
Lucy searches 1,000,000 sorted names for one name. Binary search finds it in at most 20 checks.
Why it matters
It turns a search of millions into a handful of steps. Databases and many libraries use it inside.
Full entry

In one line

Linear Search
Checking each item in turn until you find a match.
Binary Search
Finding an item in a sorted list. Each step cuts the search in half.