1. Not finding help here? Sign up for a free 30min 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 math, log base 2 (n) issues

  1. Sep 19, 2015 #1
    1. The problem statement, all variables and given/known data
    Hello!
    Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
    I would be grateful for help.

    2. Relevant equations
    For example:
    Find number 8 in the set 1234578.

    3. The attempt at a solution
    The set contains n = 7 elements.
    1) take the middle number 4; 4 < 8
    2) take the middle number in the right half of the set 7; 7 < 8
    3) in the next right half we have only 1 element and it's 8. done.

    Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
    there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

    I don't see why it is log2(n).
    Thank you!
     
  2. jcsd
  3. Sep 19, 2015 #2

    Mark44

    Staff: Mentor

    See https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance
     
  4. Sep 19, 2015 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Why would you say the set {1,2,3,4,5,6,7,8} has seven elements? Count them: there are eight of them!
     
    Last edited: Sep 19, 2015
  5. Sep 19, 2015 #4
    Ray, please, take a look at my example, it has 7 elements :) I don't have 6 in the set :)
     
  6. Sep 19, 2015 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You seem not to understand what the O notation means. If x is a variable that can become very large then O(x) is the same as O(x+1) etc.
     
  7. Sep 19, 2015 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The ##\log_2(n)## count is an asymptotic, worst-case bound. For ##n = 7## we have ##\log_2(7) \doteq 2.80735##, and no algorithm can take exactly that many steps.
     
  8. Sep 19, 2015 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper


    Right: you got me on that. Good one!
     
  9. Sep 20, 2015 #8
    Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?
     
  10. Sep 20, 2015 #9

    Mark44

    Staff: Mentor

    See https://en.wikipedia.org/wiki/Big_O_notation.
     
  11. Sep 20, 2015 #10

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    No: 2.807 is an upper bound on the number of steps, and since the actual number of steps must be an integer, we must have N(steps) ≤ 2.
     
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 math, log base 2 (n) issues
Loading...