# Binary search: the math behind 32 steps

1. Dec 8, 2015

### ducmod

1. The problem statement, all variables and given/known data

Hello!
I have just heard in one online lecture that if for example there is a phone book with 4 billion entries (or a data set
with 4 billion entries), then to find one entry (for example, Kim Simth) I need maximum 32 steps.
If the amount of entries is increased by half, ie to 8 biliion, then it's ll take 33 steps.

I understand the algorithm of how to do binary search (divide by half, by half, etc). But I have no clue on how to
compute the math behind those 32 steps, and how log(n) works in this case.

it (not in Wikipedia, sorry).

Thank you very much!

2. Dec 8, 2015

### BvU

Powers of 2 are very powerful ! Play around with 8, 16 entries to see how itt works. Note that the array has to be sorted in order to do this.

Side exercise: if there are 512 contestants at Wimbledon, how many matches have to be played until Djoko gets the first prize ? And how many rounds does that take ? Same thing !

3. Dec 8, 2015

### ducmod

I am not sure I correctly understood the nice Wimbledton side task :) Is it 9 steps in worst case scenario? 512 = 2^9, i.e. log 2( 512) = 9

4. Dec 8, 2015

### BvU

Nine rounds is right. How would you calculate the total number of matches that it takes ? (this doesn't help with your original post, but it's a nice thingy to carry with you for later on).

Back to the BS (): If it takes nine steps for 29 entries, how many steps for 232 ? How much is 232 ? The math is really simple, actually! And the number of steps is the 2 logarithm of the number of entries. Piece of cake!

5. Dec 8, 2015

### Staff: Mentor

In other words, the number of steps = $\log_2(\text{entries})$

Here $\log_2(4) = 2, \log_2(8) = 3$, and so on.