Choosing a Search Algorithm

A search algorithm is used to find a target in a collection of data. Choosing between linear search and binary search depends mainly on whether the data is sorted, how large the list is, and whether you will search it once or many times.

Unsorted data and one-off searches

Linear search works on any list, sorted or not: it starts at the first item and checks items in turn. Binary search only works once the data is sorted into order. If your data is unsorted and you only need to search it once, linear search is usually the sensible choice: sorting first would take time, and that effort only pays off if you plan to make many searches afterwards.

Large sorted lists

If a large list is already sorted, binary search is preferred. It looks at the middle item, compares it with the target, and discards the half that cannot contain the target. Each comparison removes about half of the remaining items, so it needs far fewer comparisons than linear search, which might have to check every item.

Worked example: in a sorted list of locker numbers from 1 to 320, a binary search for locker 298 compares 160, then 240, 280, 300, 290, 295, 297 and finally 298. That is eight comparisons, while linear search could check 298 lockers. Linear search can be quicker when the target is near the start, because binary search always begins in the middle. If the target is late in the list, linear search has to check almost every item, and if it is absent it checks them all.

Binary search is not always better

Binary search is more complex to write, so it is not automatically the better choice: on a short list, linear search is simpler and finds the item just as quickly. Use linear search for unsorted, small or one-off searches, and binary search for large sorted lists you search repeatedly.