Kth Smallest - Implementation (The code)

Here's the binary search on values solution:

function kthSmallest(matrix, k)
    n := number of rows in matrix
    left := matrix[0][0]
    right := matrix[n - 1][n - 1]
    while left < right
        mid := left + (right - left) / 2
        count := countLessOrEqual(matrix, mid)
        if count < k then
            left := mid + 1
        else
            right := mid
    return left

function countLessOrEqual(matrix, target)
    n := number of rows in matrix
    count := 0
    row := n - 1
    col := 0
    while row ≥ 0 and col < n
        if matrix[row][col] ≤ target then
            count := count + (row + 1)
            col := col + 1
        else
            row := row - 1
    return count

The outer binary search halves the value range, taking $O(\log(max - min))$ iterations. Each iteration calls $countLessOrEqual$, which walks the matrix in $O(n)$ time. Total: $O(n \log(max - min))$.