Binary Search

[twodayslate]

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?

[oracleguy]

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.

[Trinithis]

@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.

[ralph l mayo]

...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.)

[tman11580]

lol everyone has a diffferent answer..id help if i knew how

[oracleguy]

Originally Posted by Trinithis

@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?

[liorean]

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.

[twodayslate]

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?

[Trinithis]

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.

[ralph l mayo]

Originally Posted by twodayslate

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).

[twodayslate]

log base two n is correct.

So technically there are two answers then?

[twodayslate]

Ralph you are correct! Major props!

10 => 4
100 => 7
1000 => 10
10000 => 14
100000 => 17