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.