A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 linear search. But let’s see what happens with larger arrays.

With an array containing 100 values, here are the maximum number of steps each type of search would take:

• Linear search: 100 steps
• Binary search: 7 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 of size 100, this would take 100 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 first guess, we get to eliminate a whopping fifty cells. ...