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.
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.
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.
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.