What is the total number of comparisons necessary to locate all the n sorted distinct integers in an array using binary search? I think the number is n log2 n (2 is the base), but I am not sure. What do you think?
+3
A:
If you want an exact answer, then it is clearly not N log(N) or N log2(N). For most integers N, logN and log2 are not rational, but the number of comparisons must be an integer value.
Also, the exact answer will depend on implementation details of the binary search algorithm. For example, if a "comparison" is a simple relation that returns true and false, more comparisons are required than when a "comparison" returns negative, zero or positive. (In the latter case, you can short circuit when the algorithm hits the key early.)
Stephen C
2010-04-07 06:43:22
What tree? I see no tree :)
Billy ONeal
2010-04-07 06:52:56
@Billy - fixed that
Stephen C
2010-04-07 07:17:44
OK. Back to +1 :)
Billy ONeal
2010-04-07 07:19:42
+1
A:
It takes log2 n to find each one, and it needs to be done n times, so n log n it is.
Ignacio Vazquez-Abrams
2010-04-07 06:43:35
A:
I would say it takes n log m
Where m is the size of the array, so log m to find a value.
And then you do this n times for the n distinct integers.
So n log m in total.
dafmetal
2010-04-07 07:29:32
more detail about my question:the search algorith is:int left = 0,right = array.length()-1;while(left<=right){ int middle = (left+right)/2;if(array[middle]==key){return true;}else if(array[middle]<key){left=middle+1;}else{right = middle-1;}}return false;another assumption: we are not allowed to reuse the result from ohter searches; we can only perform each search separately.my answer should be ceiling(nlong2n) (2 is the base).
alan
2010-04-07 08:21:56
I misunderstood your question, I thought it was known in advance how many distinct integers to find (= n) in a sorted array of arbitrary length (= m). My bad.
dafmetal
2010-04-07 11:07:10
Thanks for your comments, now I am clear. I think what Stephen C said is true. I think we cannot actually work out a formula for this question unless we have a exact value. However, if the n=2^n -1,like 511(2^9 -1), it is easy to compute. For 511, total number of comparisons = 1x1 + 2X2 + 3X4 + 4X8 + 5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097.
alan
2010-04-07 17:25:45
A:
There will be at most (2 * log2n + 1) rounded down(so 7.6 => 7) comparisons for 1 number.
When we land on some number in array, first we check if it is the one we are looking for. (== first comparison). After that we check if it smaller (or greater) (second comparison).
To find the number, we must process at most log2n numbers.
And we must make the last comparison on the last number, to check that this is the one.
So looking for 16 in [1..16] will take 2*log216 + 1 = 9 comparisons (assuming we land on these numbers: 8, 12, 14, 15, 16). And looking for 10 in [1..10] will take 2*log210 + 1 = 7.6 => 7 (Assuming we land on these numbers: 5, 8, 9, 10).
So for n numbers there will be at most n times more.
Draco Ater
2010-04-07 08:33:41
A:
Thanks for your comments, now I am clear. I think what Stephen C said is true. I think we cannot actually work out a formula for this question unless we have a exact value. However, if the n=2^n -1,like 511(2^9 -1), it is easy to compute. For 511, total number of comparisons = 1x1 + 2X2 + 3X4 + 4X8 + 5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097.
alan
2010-04-07 17:26:09