a bit of codeforces: Multiplication Table (Interesting Binary Search)

Problem Statement:
448 D - Multiplication Table

Summary:
Given a table of dimension M x N, where $1 \leq M,N \leq 10^5$, and with the property that cell $i,j$ contains $i*j$, find the $k$-th largest element in the table.

We can certainly generate all $i*j$ and store them inside a vector, and simply iterate through to the $k$-th element ($O(N^2)$), but that will take forever when $M,N$ are large. Furthermore, we actually can perform a very cool binary search to find the k-th element! Firstly, notice that if we are given a number $S$, we can find its rank in $O(N)$ time by simply checking on each row how many cells are less than or equal to $S$ (we will actually end up with the largest rank of $S$ if $S$ occurs several times on the table). After obtaining the rank, we can check whether it is less than or bigger than $k$, and we perform a corresponding binary search until we end up with the correct value of S. The approach is therefore $O(N\lg{N})$ which is fast enough for the time limit.