Home | Bookmarks | Papers | Blog |

Caveat Emptor - the fact that google returns this page as one of the hits on median computation, does not mean this information is reliable. It is not! A better place to look would be somewhere else (I am too lazy to find the right reference, OK?).

Let

`FindKMedian( A, K )`

- Pick randomly a number
**a**from**A = {a**._{1}, ..., a_{n}} - Partition the
**n**numbers into two sets:**S**- all the numbers smaller than**a****B**- all the numbers bigger than**a**

- If
**|S| = K-1**then**a**is the required K-median. Return**a** - If
**|S| < K-1**then the**K**-median lies somewhere in**B**. Call recursively to`FindKMedian( B, K - |S| - 1 )` - Else, call recursively to
`FindKMedian( S, K )`.

Back to the linear programming applet