Have Geek Brain

How many numbers in the array are less than a given number?

Naive is O (n). Is there one that is O (log n) or even O (1)?

How about a sorted array? How about using a binary search tree?

How about my array is of size n = [2 ^ (h + 1)] - 1? // h = the height of the full binary tree

+2


a source to share


2 answers


Unsorted
If the array is not sorted, you can do no better than O (n). Evidence. Suppose you did not look at every element of the array, then the enemy could simply make one of the elements that you did not look at more or less than a given number to make your count wrong. So no better than O (n) is impossible.



Sorting
If the array is sorted, then you can define the result in O (log n) by setting the first element that is greater than or equal to the specified number, and then simply subtracting that index from the size of the array.

+8


a source


With unsorted, you can't do better than O (n). The final.

When sorting, you can do worst case O (log (n)) with binary search. You can now improve on this, assuming the array layout has either decent entropy or (mostly) linear, focusing on the expected point as if the layout were purely linear.



For example, take a sorted array a [n] with [0] = x, a [n] = y and your threshold v. Instead of dividing the array in half for n / 2, the test item is a [n * (vx) / (yx)] With regular layout (a [i] = const1 * i + const2) you get the result in O (1), one error + - rounding, so the worst case is 2. With a random arrangement of "white noise" (all values ​​are equally likely), you get it much faster than O (log (n)).

0


a source






More articles:


All Articles