A Common-Sense Guide to Data Structures and Algorithms

Binary Search vs. Linear Search

With ordered arrays of a small size, the algorithm of binary search doesn’t have much of an advantage over the algorithm of linear search. But let’s see what happens with larger arrays.

With an array containing one hundred values, here are the maximum numbers of steps it would take for each type of search:

• Linear search: one hundred steps
• Binary search: seven steps

With linear search, if the value we’re searching for is in the final cell or is greater than the value in the final cell, we have to inspect each and every element. For an array the size of 100, this would take one hundred steps.

When we use binary search, however, each guess we make eliminates half of the possible cells we’d have to search. In our very ...