monotone matrix search: sorted matrix $M$ of size $m\times n$. given a number $x$. find the largest element in $M$ smaller than $x$.

semimonotone matrix search: monotone matrix search but only rows are sorted.

monotone matrix selection: sorted matrix $M$ of size $m\times n$. given a number $x$. find the $k$th smallest element in $M$.

(semi)monotone matrix search with oracle: comparison between the target $x$ and elements in the matrix has to be done through an oracle while comparison between two matrix elements still take $O(1)$ time.

### monotone matrix search

straight forward fractional cascading $O(mn)$ for preprocessing and $O(\min(m,n)+\log \max(m,n))$ for the search. Actually if the cols of the matrix $m$ is not sorted then fractional cascading is optimal(i think...) 2/22 update. for semi-monotone matrix search there is no significantly better algorithm than do n binary search if no preporcessing allowed. see the lowerbound part in https://mediatum.ub.tum.de/node?id=1094388

### monotone matrix selection

https://chaoxu.prof/posts/2014-04-02-selection-in-a-sorted-matrix.html chao says this is very similar to fractional cascading but i understand it in a slightly different way. First observe an important inequality which allow you to find the $k$th element recursively.(with a little more work, do a selection) This is more similar to median of medians(linear top k alg).
### seach problems with oracle
see https://chaoxu.prof/posts/2019-01-30-search-sorted-matrix.html and again they have the optimal solution https://mediatum.ub.tum.de/node?id=1094388 . The idea for monotone matrix search is the following. Assume the matrix is $n\times n$ and $n=2^k-1$. Take the submatrix if both coordinates of some element are divisible by $2^i$.


there are 3 submatrix in the picture.

If for the small submatrix we know the boundary between elements smaller than $x$ and larger than $x$ how many elements is needed to check in order to know the boundary for the larger submatrix?

One can see that there will be at most one element in each row/col/diag of the larger submatrix. so in total we need to check $\sum_{i=1}^k (2^i+2^i+2\cdot 2*i)\leq 8n$ elements in the matrix. see the paper for more detail.