A Common-Sense Guide to Data Structures and Algorithms

The pattern that emerges is that for every time we double the number of items in the ordered array, the number of steps needed for binary search increases by just one. This pattern is unusually efficient: for every time we double the data, the binary search algorithm adds a maximum of just one more step. Contrast this with linear search. If you had three items, you’d need up to three steps. For seven elements, you’d need a maximum of seven steps. For one hundred, you’d need up to one hundred steps. With linear search, there are as many steps as there are items. For linear search, every time we double the number of elements in the array, we double the number of steps we need to find something. For binary search, every time we double the number of elements in the array, we only need to add one more step.