The naive one is O(n). Is there a one that is O(log n) or even O(1)?
How about a sorted array? How about using binary search tree?
How about my array has a size n = [2 ^(h + 1)] − 1 ? // h=height of a complete binary tree
+7
A:
Unsorted
If the array is not sorted, then you can do no better than O(n). Proof: suppose you didn't look at every single element of the array, then an adversary could just make one of the elements that you didn't look at larger or smaller than the given number to make your count incorrect. So, better than O(n) is not possible.
Sorted
If the array is sorted, then you can determine the result in O(log n) time by locating the first element that is greater than or equal to the given number, and then simply subtracting that index from the size of the array.
Michael Aaron Safyan
2010-04-26 02:23:38
@caf how so -- you can still do a binary search for that.
WhirlWind
2010-04-26 02:40:03
To improve on what Micheal said, the best result would be a binary search, which would search for the element equal to the given element, then just iterate up the array until a large value is reached.
Grue
2010-04-26 02:56:54
@Grue if you do binary search, you don' t need to iterate up the array. You just need to know the number of elements in it.
San Jacinto
2010-04-26 03:00:02
@Grue: No, you can do better than just "iterating up until a large value is reached". For example, `std::lower_bound` is O(lg n) no matter how large the range of equal values is.
Billy ONeal
2010-04-26 03:00:55
A:
With unsorted, you can't do better than O(n). Final.
With sorted, you can do in worst case O(log(n)) with binary search. Now you can improve upon this assuming the array layout has either decent entropy or is (mostly) linear by aiming at expected point as if the layout was purely linear.
For example, take a sorted array a[n] with a[0]=x, a[n]=y, and your threshold v. Instead of bisecting the array at n/2, test element of a[n*(v-x)/(y-x)] With regular layout (a[i] = const1*i+const2) you get the result in O(1), one hit +- rounding error, so at worst 2. With "white noise" random layout (all values equally probable), you get it still much faster than O(log(n)).
SF.
2010-04-29 11:52:01