Max Comparisons in Binary Search: Understanding Efficiency and Implementation

[MinusTheBear]

I have two questions over linear and binary serch.

1. Homework Statement
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 ___.

Homework Equations

n/a

The Attempt at a Solution

Q1: I know that 2ⁿ = # of elements, where n is the maximum number of comparisons required; or that log₂(# 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 log₂(# 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.

 

[LCKurtz]

I have two questions over linear and binary serch.

1. Homework Statement
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 ___.

Homework Equations

n/a

The Attempt at a Solution

Q1: I know that 2ⁿ = # of elements, where n is the maximum number of comparisons required; or that log₂(# 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.

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.

 

[MinusTheBear]

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.

ahhh gotcha. It'd be (1/2)³. Thanks