Search algorithms: linear and binary

Searching means finding a required element in a collection or finding out that it is not there. The simplest method is linear search: elements are checked one by one from the start, and the search stops when the element is found. It works on any list, but in the worst case all n elements must be examined. In Python, for a list, x in a and a.index(x) work exactly like this.

Binary search works only on a sorted array. It compares the target with the middle element: if the target is smaller, the right half is discarded, and if it is larger, the left half. The process repeats on the remaining part, so at each step the search area shrinks by about half. The middle index is found with mid = (low + high) // 2.

Let us search for 23 in the sorted array 2 5 8 12 16 23 38 56 72 91. In step 1 the middle element 16 is smaller than the target, so the search continues in the right half (23 38 56 72 91). In step 2 the middle element 56 is larger, so the left part (23 38) remains; in step 3 the middle element equals 23 and the number is found.

In linear search the number of comparisons is proportional to the number of elements, while binary search needs at most about log2 n. For example, in a sorted array of 1,000,000 elements binary search takes at most 20 steps, while linear search makes up to a million comparisons. However, if the array first has to be sorted, linear search is simpler for a single lookup; for many lookups it pays to sort once and then use binary search.

Key takeaways

• Linear search checks elements one by one and works on any list.
• Binary search works only on a sorted array.
• Binary search cuts the search area roughly in half at every step.
• For 1,000,000 elements binary search takes at most 20 steps, while linear search makes up to a million comparisons.
• Before many searches, it pays to sort the array once.