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: Linear and Binary Search

  1. Mar 3, 2017 #1
    I have two questions over linear and binary serch.

    1. The problem statement, all variables and given/known data

    Q1: In binary search, after three comparisons have been made, only ___ of the array will be left to search.
    Q2: The maximum number of comparisons that a binary search function will make when searching for a value in a 2,000-element array is ___.

    2. Relevant equations

    3. The attempt at a solution
    Q1: I know that 2n = # of elements, where n is the maximum number of comparisons required; or that log2(# of elements) = n

    I'm assuming that you're using n = 3, but I'm not sure how the book gets the answer of 1/8.

    Q2: I know the answer here is 11 based on log2(# of elements) = n, where n is the maximum number of comparisons. My question is, however, is it always ceil(n)? It would make sense since were dealing with a maximum but the book doesn't say other than that it's an exponential function.

    This is an intro course to C++ so I'm sure that's why they don't go super in depth.
  2. jcsd
  3. Mar 3, 2017 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    How much is left after the first comparison? After the second? The third? You don't need logs or exponents to figure this one out.
  4. Mar 3, 2017 #3
    ahhh gotcha. It'd be (1/2)3. Thanks
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted