# Homework Help: Linear and Binary Search

Tags:
1. Mar 3, 2017

### MinusTheBear

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
n/a

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. Mar 3, 2017

### LCKurtz

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.

3. Mar 3, 2017

### MinusTheBear

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