So here’s an interesting problem: *Given an NxM integer matrix in which each row is sorted, find the overall median of the matrix assuming N*M is odd*. For example,

# Tag Archives: selection

# Randomized selection algorithm

The problem is to find the i^{th} order statistic (i.e., i^{th} smallest element) in an input array. This algorithm is a modification of quicksort and takes time O(n), on average, on an input array of size n.