Searching Algorithms
A searching algorithm is a set of clear steps for finding a particular piece of data inside a collection — like looking up a name in a contacts list or a product in an online shop. Two standard searching methods appear again and again in computing: the linear search and the binary search. Both reach the same goal — locating an item — but they go about it in very different ways, and each one suits different situations.
Linear search
A linear search is the most straightforward method. It starts at the very first item in the list and compares it with the target — the value being searched for. If the two match, the search is over and the position is reported. If they do not match, the algorithm simply moves on to the next item and compares again.
This checking continues, one item at a time, until either the target is found or the end of the list is reached. If the end is reached without a match, the algorithm reports that the item is not in the list. Because it never assumes anything about the order of the data, a linear search works on any list at all.
A linear search has no prerequisites: it works whether the data is sorted or not. That makes it flexible, but it can be slow because it may have to check every single item.
How efficient is it? Each time the algorithm checks one item against the target, that counts as one comparison. In the best case the target is the first item, so only one comparison is needed. In the worst case the target is the last item — or missing entirely — and the algorithm must make as many comparisons as there are items in the list.
Imagine searching the unsorted list 34, 7, 19, 45, 2, 88 for the value 45. The algorithm checks 34 (no match), then 7 (no match), then 19 (no match), then 45 — a match, found at the fourth position after four comparisons. If instead we searched for 15, the algorithm would check all six items, reach the end without a match, and report that 15 is not in the list. Notice that the list did not need to be in order for this to work.
Binary search
A binary search is much faster, but it comes with one strict condition: the list must already be sorted, meaning the items are arranged in order such as numbers from smallest to largest. When the data is sorted, a binary search can rule out huge chunks of the list at once instead of plodding through it item by item.
It works by finding the middle item of the list and comparing it with the target. If they match, the search is finished. If the target is smaller than the middle item, the algorithm throws away the middle item and the entire upper half, then repeats on the lower half. If the target is larger, it throws away the lower half and repeats on the upper half. Each pass finds a new middle and discards half of what remains, until the item is found or nothing is left to check.
A binary search only works on sorted data, and it halves the number of items still to check with every comparison. That is why it is so fast on large lists.
Suppose the sorted list is 2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91 and we are looking for 45. First the algorithm checks the middle value, 23. Because 45 is larger than 23, the whole lower half is discarded and only 38, 45, 56, 72, 91 remain. The new middle value is 56; 45 is smaller, so 56 and everything above it is discarded, leaving 38 and 45. The middle of these two rounds down to 38; 45 is larger, so only 45 is left, and the next check finds it. The target was found in just four comparisons, whereas a linear search would have taken eight.
Comparing the two searches
The big difference is speed on large lists. A linear search may have to look at every item, so searching a list of one thousand items could take up to one thousand comparisons. A binary search halves the remaining items with every check, so the same list of one thousand items needs at most about ten comparisons. It scales remarkably well: doubling the size of the list adds only one extra comparison to a binary search.
So why not always use a binary search? Because it only works on a sorted list. If the data is not in order, it must be sorted first, and sorting takes time and effort. A linear search has no such requirement — it happily works on data in any order and is very simple to write. For short lists the speed difference is tiny, so the extra work of keeping data sorted may not be worth it.
If the data set is small, or if it changes often and is rarely kept in order, a linear search is usually the sensible choice because it is simple and needs no preparation. If the data is large and already sorted — or will be searched many times — a binary search is far more efficient. Remember that sorting a list takes time too, so a binary search pays off most when the same sorted list is searched again and again.