1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Binary search: the math behind 32 steps

  1. Dec 8, 2015 #1
    1. The problem statement, all variables and given/known data

    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!
  2. jcsd
  3. Dec 8, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    2017 Award

    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 !
  4. Dec 8, 2015 #3
    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
  5. Dec 8, 2015 #4


    User Avatar
    Science Advisor
    Homework Helper
    2017 Award

    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 (:smile:): 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!
  6. Dec 8, 2015 #5


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted