Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 12 of 12

Thread: Binary Search

  1. #1
    Senior Coder twodayslate's Avatar
    Join Date
    Mar 2007
    Location
    VA
    Posts
    1,042
    Thanks
    67
    Thanked 39 Times in 39 Posts

    Binary Search

    How many times would the binary search (O(logn)) loop, assuming you did not find the data, if:
    n = 10? 3
    n = 100? 6
    n = 1000? 12
    n = 10,000? 18
    n = 100,000? 24
    n= number of elements in array. My answers are above. Are they correct?
    Last edited by twodayslate; 09-08-2008 at 01:46 AM.
    twitter | Quality Hosting - $5.95/mo*
    Feel free to PM me!

  • #2
    Rockstar Coder
    Join Date
    Jun 2002
    Location
    USA
    Posts
    9,074
    Thanks
    1
    Thanked 328 Times in 324 Posts
    I got:
    1
    2
    3
    4
    5

    But it has been a while since I've done big O notation so I might have goofed it up.
    OracleGuy

  • Users who have thanked oracleguy for this post:

    twodayslate (09-08-2008)

  • #3
    Regular Coder
    Join Date
    Jun 2007
    Location
    USA
    Posts
    527
    Thanks
    26
    Thanked 74 Times in 72 Posts
    @oracleguy: log in cs typically denotes the natural log (aka ln)

    Here are the answers.

    10 : 3
    100 : 5
    1000 : 7
    10000 : 10
    100000 : 12

    EDIT: should be "denotes the log base 2" Thus my answers are wrong for log base 2.
    Last edited by Trinithis; 09-08-2008 at 11:40 PM.
    Trinithis

  • Users who have thanked Trinithis for this post:

    twodayslate (09-08-2008)

  • #4
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    ...but the actual worst-case performance of the binary search is the binary logarithm of n, O(log2 n). Trick question?

    ceil(log2 n == log n/log 2) =
    10 => 4
    100 => 7
    1000 => 10
    10000 => 14
    100000 => 17

    (the answer is supposed to round up, right? the actual number depends on which bound the missing search value is closest to and how the implementation rounds when picking midpoints.)
    Last edited by ralph l mayo; 09-08-2008 at 09:23 AM.

  • Users who have thanked ralph l mayo for this post:

    twodayslate (09-08-2008)

  • #5
    New Coder
    Join Date
    Sep 2008
    Location
    new york
    Posts
    13
    Thanks
    2
    Thanked 0 Times in 0 Posts
    lol everyone has a diffferent answer..id help if i knew how

  • #6
    Rockstar Coder
    Join Date
    Jun 2002
    Location
    USA
    Posts
    9,074
    Thanks
    1
    Thanked 328 Times in 324 Posts
    Quote Originally Posted by Trinithis View Post
    @oracleguy: log in cs typically denotes the natural log (aka ln)
    Oh ok; that is kind of dumb. If it is supposed to be the natural log why not just write ln and be mathematically correct?
    OracleGuy

  • Users who have thanked oracleguy for this post:

    twodayslate (09-08-2008)

  • #7
    Master Coder
    Join Date
    Feb 2003
    Location
    UmeŚ, Sweden
    Posts
    5,575
    Thanks
    0
    Thanked 83 Times in 74 Posts
    Because just writing log you don't tell anybody which logarithm you're talking about - the default assumption is for that reason the most useful one, in other words the natural logarithm.

    Which logarithm do you consider a better default? Decimal? Binary? The binary logarithm is at least somewhat useful for many algorithms, the decimal logarithm less so.
    liorean <[lio@wg]>
    Articles: RegEx evolt wsabstract , Named Arguments
    Useful Threads: JavaScript Docs & Refs, FAQ - HTML & CSS Docs, FAQ - XML Doc & Refs
    Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards

  • Users who have thanked liorean for this post:

    twodayslate (09-08-2008)

  • #8
    Senior Coder twodayslate's Avatar
    Join Date
    Mar 2007
    Location
    VA
    Posts
    1,042
    Thanks
    67
    Thanked 39 Times in 39 Posts
    I have not learned decimal so IDK about that...

    So what is the right answer? ralph looks the closest...

    Here are the steps for 10?
    10
    5
    3
    1


    So 3 is correct?
    Last edited by twodayslate; 09-08-2008 at 11:22 PM.
    twitter | Quality Hosting - $5.95/mo*
    Feel free to PM me!

  • #9
    Regular Coder
    Join Date
    Jun 2007
    Location
    USA
    Posts
    527
    Thanks
    26
    Thanked 74 Times in 72 Posts
    Wow, I'm dumb too. I meant log base 2, not ln . . . and I did my calculations using ln instead of log2. ralph's answers are the ones I would use.

    Another reason why people just say log instead of log base x is due to the fact that big O (and family) factors out the constant factors and all logs are just some constant factor of one another.
    Trinithis

  • #10
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    Quote Originally Posted by twodayslate View Post
    I have not learned decimal so IDK about that...

    So what is the right answer? ralph looks the closest...

    Here are the steps for 10?
    10
    5
    3
    1


    So 3 is correct?
    No, the steps for 10 with that rounding scheme (ceil or closest, assuming the search is for 0) are:
    5
    3
    2
    1

    Or if it rounds to the floor:
    5
    2
    1

    100, ceil or closest:
    50
    25
    13
    7
    4
    2
    1

    100, floor:
    50
    25
    12
    6
    3
    1

    I'm pretty sure my numbers are correct for actual implementations of the binary search, but they don't reflect O(log n), rather O(log2 n).

  • #11
    Senior Coder twodayslate's Avatar
    Join Date
    Mar 2007
    Location
    VA
    Posts
    1,042
    Thanks
    67
    Thanked 39 Times in 39 Posts
    log base two n is correct.

    So technically there are two answers then?
    twitter | Quality Hosting - $5.95/mo*
    Feel free to PM me!

  • #12
    Senior Coder twodayslate's Avatar
    Join Date
    Mar 2007
    Location
    VA
    Posts
    1,042
    Thanks
    67
    Thanked 39 Times in 39 Posts
    Ralph you are correct! Major props!

    10 => 4
    100 => 7
    1000 => 10
    10000 => 14
    100000 => 17
    twitter | Quality Hosting - $5.95/mo*
    Feel free to PM me!


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •