Binary search: the math behind 32 steps

[ducmod]

Homework Statement

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.

Please, help me with your advice on how to learn this, what are good resources on this matter, where to read about
it (not in Wikipedia, sorry).

Thank you very much!

 

[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 !

 

[ducmod]

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 !

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

 

[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 2⁹ entries, how many steps for 2³² ? How much is 2³² ? The math is really simple, actually! And the number of steps is the 2 logarithm of the number of entries. Piece of cake!

 

[Mark44]

And the number of steps is the 2 logarithm of the number of entries.

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

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