Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 12 of 12
Thread: Binary Search

09082008, 01:42 AM #1
Binary Search
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?Last edited by twodayslate; 09082008 at 01:46 AM.

09082008, 05:06 AM #2
 Join Date
 Jun 2002
 Location
 USA
 Posts
 9,074
 Thanks
 1
 Thanked 328 Times in 324 Posts
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.OracleGuy

Users who have thanked oracleguy for this post:
twodayslate (09082008)

09082008, 07:40 AM #3
 Join Date
 Jun 2007
 Location
 USA
 Posts
 527
 Thanks
 26
 Thanked 74 Times in 72 Posts
@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.Last edited by Trinithis; 09082008 at 11:40 PM.
Trinithis

Users who have thanked Trinithis for this post:
twodayslate (09082008)

09082008, 09:16 AM #4
...but the actual worstcase 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.)Last edited by ralph l mayo; 09082008 at 09:23 AM.

Users who have thanked ralph l mayo for this post:
twodayslate (09082008)

09082008, 12:15 PM #5
 Join Date
 Sep 2008
 Location
 new york
 Posts
 13
 Thanks
 2
 Thanked 0 Times in 0 Posts
lol everyone has a diffferent answer..id help if i knew how

09082008, 04:06 PM #6
 Join Date
 Jun 2002
 Location
 USA
 Posts
 9,074
 Thanks
 1
 Thanked 328 Times in 324 Posts

Users who have thanked oracleguy for this post:
twodayslate (09082008)

09082008, 10:40 PM #7
 Join Date
 Feb 2003
 Location
 Umeå, Sweden
 Posts
 5,575
 Thanks
 0
 Thanked 83 Times in 74 Posts
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.liorean <[lio@wg]>
Articles: RegEx evolt wsabstract , Named Arguments
Useful Threads: JavaScript Docs & Refs, FAQ  HTML & CSS Docs, FAQ  XML Doc & Refs
Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards

Users who have thanked liorean for this post:
twodayslate (09082008)

09082008, 11:12 PM #8
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?Last edited by twodayslate; 09082008 at 11:22 PM.

09082008, 11:37 PM #9
 Join Date
 Jun 2007
 Location
 USA
 Posts
 527
 Thanks
 26
 Thanked 74 Times in 72 Posts
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.Trinithis

09082008, 11:38 PM #10
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).

09082008, 11:56 PM #11
log base two n is correct.
So technically there are two answers then?

09102008, 02:12 AM #12
Ralph you are correct! Major props!
10 => 4
100 => 7
1000 => 10
10000 => 14
100000 => 17