# Binary search math, log base 2 (n) issues

1. Sep 19, 2015

### ducmod

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. Sep 19, 2015

### Staff: Mentor

See https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance

3. Sep 19, 2015

### Ray Vickson

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
4. Sep 19, 2015

### ducmod

Ray, please, take a look at my example, it has 7 elements :) I don't have 6 in the set :)

5. Sep 19, 2015

### haruspex

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.

6. Sep 19, 2015

### Ray Vickson

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.

7. Sep 19, 2015

### Ray Vickson

Right: you got me on that. Good one!

8. Sep 20, 2015

### ducmod

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?

9. Sep 20, 2015

### Staff: Mentor

See https://en.wikipedia.org/wiki/Big_O_notation.

10. Sep 20, 2015

### Ray Vickson

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.