Find median in a sorted matrix

Question

Suppose we are given a $n\times n$ matrix that is sorted row-wise and column-wise. We want to find the median in $\mathcal{O}(n\log{n})$.

This is my approach:
We know median is such element that is greater than exactly $\lfloor\frac{n^2-1}{2}\rfloor$ elements.
In such matrix, we always know that minimum value is the first element and the maximum value is the last element. So we declare and initialize two variables $\texttt{min}$ and $\texttt{max}$. Then we put $\texttt{mid} = \frac{\texttt{min}+\texttt{max}}{2}$. Afterwards, we're going to count the number of elements that are lower than $\texttt{mid}$ using binary search. For each row, the binary search can be done in $\mathcal{O}(\log{n})$ and we're doing it on $\mathcal{O}(n)$ rows. So this part takes $\mathcal{O}(n\log{n})$ time. If number of smaller elements than $\texttt{mid}$ is lower than $\lfloor\frac{n^2-1}{2}\rfloor$, then we put $\texttt{min}=\texttt{mid}+1$. Otherwise we put $\texttt{max}=\texttt{mid}$. Then recurse with new $\texttt{min}$ and $\texttt{max}$ values. The condiction to stop is when $\texttt{min}\geq\texttt{max}$. Then we return $\texttt{min}$.

Time complexity analysis:
According to the algorithm I explained, the recurrence relation should be: $$T(n)=T(\frac{n}{2})+\mathcal{O}(n\log{n}).$$ Using Master's Theorem, we can conclude $T(n)=\mathcal{O}(n\log{n})$. So we're done.

I want to know:

• Is my algorithm correct?
• Is the time complexity analysis correct?
• I know the algorithm is not explained accurate enough. For example I don't know I should count elements that are strictly smaller than $\texttt{mid}$, or I should also count elements that are equal to $\texttt{mid}$. Also when checking if the smaller elements are $<$ or $\leq $ than $\lfloor\frac{n^2-1}{2}\rfloor$.

Any helps are immensley valuable to me.

EDIT.

I found a problem in the algorithm. What if $\texttt{min}$ is not an element existing in the array? How can I solve the problem?

Answer 1

Probably main problem I see is recursion being made on values

we put $mid=\frac{min+max}{2}$

If number of smaller elements than mid is lower than $\frac{n^2−1}{2}$, then we put min=mid+1. Otherwise we put max=mid. Then recurse with new min and max values. The condition to stop is when min≥max. Then we return min.

every step halves $max - min$ - and we have no information on size of that

example of worst case would be correctly placed distinct powers of 2 - halving $max-min$ would prune only 1 element at a time

Answer 2

Is the time complexity analysis correct? no. you changed what n means when you included the master theorem. The runtime of this algorithm is O(n^2*log(n))

This algorithm does technically work, but it's a really dumb way of doing it (since at the very least the median of an unsorted list (of n^2 numbers) can be found in O(n^2) time). With the structure you have, I'm pretty sure there exists an algorithm that computes the median in O(n) time but doing so will be a little tricky.

Answer 3

The algorithm proposed by Mirzaian and Arjomandi (A. Mirzaian, E. Arjomandi, Selection in X + Y and matrices with sorted rows and columns, Information Processing Letters, Volume 20, Issue 1, 1985, Pages 13-17, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(85)90123-1) can compute any order statistics, including the median, in $O(n)$.

Let $A$ be a matrix of real numbers, whose order is $n$ and in which the rows are sorted in descending order and the columns are sorted in ascending order. Moreover, let $\overline{n} = \lceil \frac{1}{2} (n+1) \rceil$. Then $\overline{A}$ is a submatrix of $A$ of order $\overline{n}$, consisting of the odd indexed rows and columns (plus the last row and columns of $A$ if $n$ is even). Letting $L$ be a list of reals and $a$ a real number, the $rank^+$ and $rank^-$ of $a$ in the list $L$ are defined as follows:

$rank^+(L,a) = |\{x \in L:x>a\}|$;

$rank^-(L,a) = |\{x \in L:x<a\}|$.

For $1 \leq k \leq |L|$, $a$ is the $k$th smallest item of $L$ if and only if $rank^-(L,a) \leq k-1$ and $rank^+(L,a) \leq |L|-k$. The selection algorithm is based on Theorem 3.1 in the paper, which states that, given the matrices $A$ and $\overline{A}$, for any real number $a$ it holds that (i) ${rank^-(A,a) \leq 4 \ rank^-(\overline{A},a)}$ and (ii) ${rank^+(A,a) \leq 4 \ rank^+(\overline{A},a)}$.

Determining $rank^-(A,a)$ can be done in $O(n)$ taking advantage of the fact that the rows and columns of $A$ are sorted respectively in descending and ascending order. Algorithm 1 shows how to compute $rank^-(A,a)$. Similarly, $rank^+(A,a)$ can be determined in $O(n)$ as well.

To select the $k$th item, the algorithm determines two items $a$ and $b$ with $a \geq b$ from $\overline{A}$. Letting $z$ denote the $k$th order statistic of $A$, the algorithm ensures that (i) $b \leq z \leq a$ and (ii) the number of items of $A$ whose value is less than $a$ and greater than $b$ is $O(n)$. The function MAselect (Mirzaian and Arjomandi Select), shown in pseudocode as Algorithm 2, determines the $k$th item of $A$ in $O(n)$.

MAselect simply calls the biselect function (Algorithm 3) with parameters $s$, $A$, $k_1$ and $k_2$, with $k_1 \geq k_2$. The pair $(x, y)$ is returned, so that $x$ is the $k_1$th item of $A$ whilst $y$ is the $k_2$th item.

Defining

$\overline{k_1} = \begin{cases} n + 1 + \lceil \frac{1}{4} k_1 \rceil & \quad \text{if } n \text{ is even}\\ \lceil \frac{1}{4} k_1 + 2 n + 1 \rceil & \quad \text{if } n \text{ is odd} \end{cases}$

and

$\overline{k_2}=\left\lfloor\frac{1}{4}\left(\mathrm{k}_{2}+3\right)\right\rfloor$

$\overline{k_1}$ is the smallest integer such that the $\overline{k_1}$th item of $\overline{A}$ is at least as large as the $k_1$th item of $A$, and $\overline{k_2}$ is the largest integer such that the $\overline{k_2}$th item of $\overline{A}$ is no larger than the $k_2$th item of $A$.

The QuickSelect algorithm is Hoare's selection algorithm, which works in expected $O(n)$ time.

Answer 4

As non-unique values complicate things, let's keep to unique ones here.

[determine] the number of elements that are lower than [split:] For each row, a binary search can be done in O(logn)[, doing it on n rows] takes O(nlogn) time.
True, and about the best I expect when values are (guaranteed to be) ordered in each row, only.
With values ordered in each column, too, an amortised analysis should apply.
Assuming ordered ascendantly:
Let's start at the(some) middle element with a value used for the first split. The element to the right is known to be greater (all elements except split neither left nor up, actually, placing split well in the "middle half" of values), so continue with the diagonal neighbour right-up, continuing up until hitting a lower value or the top row, n/2 steps up, at most. From a value lower than split, go right until hitting a value no less than split or the rightmost column for at most another n/2 steps, a subtotal of n steps. Symmetrically for down&left for a total of 2n steps. (Speed up using exponential/binary search as seen fit.)

---

The hard part is continuing from this first boundary between less than split and no less.
"Shifting the index by one" in individual rows(columns) would seem to imply "$n^2$", with a possible factor of $O(\log n)$ for picking from a priority queue.
Finding a sequence of split values guaranteed to be dominated in length by $O(n)$ looks challenging - think of an adversary picking element values.