How many numbers in an array are smaller than a given number?

The naive one is O(n). Is there a one that is O(log n) or even O(1)?

How about a sorted arr开发者_如何学Cay? 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

---

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.

---

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