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!

Binary search: the math behind 32 steps

  1. Dec 8, 2015 #1
    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.

    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

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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

    Mark44

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Binary search: the math behind 32 steps
  1. Binary Search tree (Replies: 5)

Loading...