Suppose you have a sorted list of 128 names, and you’re searching through it using binary search. What’s the maximum number of steps it would take?

If you were using a simple search where you start from the beginning of the list of names and read each one until you find (or until you do not find) that given name — the maximum number of steps would be 128.

Binary search starts at the center of the list and then compares the given name to the name it landed on and cancels out half of the remaining list with each failed comparison. Of course, for a binary search to work, the elements of the list must be in a consistent ascending or descending order, whether alphabetical or numerical.

So, the real question we are answering is this: how many times does 2 multiply itself to equal 128?

2 x 2 = 4 x 2 = 8 x 2 = 16 x 2 = 32 x 2 = 64 x 2 = 128.

That maximum number of steps to find a given name in a list of 128 names is 7 using binary search.

Until next time, Ggs.