Search strategies: linear search vs binary search

You need to find a specific customer in a list of 1,000 names.

Unsorted list: You must check one name at a time. In the worst case, this requires 1,000 checks. This is called linear search.

Sorted list: You start in the middle. Is the name before or after? You can then eliminate half the list. Repeat the process. This is called binary search — and it requires only 10 checks for 1,000 names.

Therefore, sorting data first is often efficient if you plan to search the dataset many times.

Count the halvings: How many times can you halve 1,000 before you reach 1?

1,000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Ten steps.

Number of items	Linear search (worst case)	Binary search
10	10	4
1,000	1,000	10
1,000,000	1,000,000	20

One million items in twenty checks. This is why phone directories, dictionaries, and database indexes are sorted.

Example of the strategy: Imagine you are looking for a number between 1 and 100. If you always choose the middle (50, then 25 or 75 …), you will find the number in at most seven steps — every time.