Geek Answers Handbook

Find the median in O (log n)

The question is how can we find the median of the receiving stream of integer values ​​(for example, for 12, 14, 252, 243, 15 the median is 15) in O (log N), where N is the number of values. Please note that we have a stream of integer values, therefore, getting each value, we must re-find the median.

Example:

  | Input | median
1 |   12  |   12
2 |   14  |   13 = (12+14)/2
3 |   252 |   14
.
.
.

PS: an example of using this algorithm is image filtering.

+5
source share
3 answers

Ok, with updating the question, so that the goal is clear (not just finding the median, but finding the median again every time you get a new number), I think there is a way.

: - -. , , , - , , . , . , , - -. - .

, , . : , ( ) . ( ).

, . , , . , ( , , , ) , , .

, , / O (log N). , .

+14

( , , , n , , n + 1 , n O (n lg n).)

, , : - , . node, child/parent, , , node ( node, ). , ​​ , . , , , .

( , , .)

+4

Hoare ( ) O (n) .

It basically recursively shares the dataset with a random rod and checks the corresponding part. There is also a median median algorithm that guarantees O (n) the worst time complexity, but for normal use it is usually overkill.

+2
source

More articles:


All Articles