...

View Full Version : Binary Search

twodayslate
09-08-2008, 01:42 AM
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
09-08-2008, 05:06 AM
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
09-08-2008, 07:40 AM

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
09-08-2008, 09:16 AM
...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
09-08-2008, 12:15 PM
lol everyone has a diffferent answer..id help if i knew how :(

oracleguy
09-08-2008, 04:06 PM

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
09-08-2008, 10:40 PM
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
09-08-2008, 11:12 PM
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
09-08-2008, 11:37 PM
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
09-08-2008, 11:38 PM
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
09-08-2008, 11:56 PM
log base two n is correct.

So technically there are two answers then?

twodayslate
09-10-2008, 02:12 AM
Ralph you are correct! Major props!

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