Kth Smallest - The Insight (Binary search on values)

Binary search doesn't have to search indices. You can search the value space. Here, the smallest element is $matrix[0][0]$ and the largest is $matrix[n-1][n-1]$.

For any value $mid$, you can count how many matrix elements are $\leq mid$ by walking from the bottom-left corner. If the count is $< k$, search higher values. If $\geq k$, search lower values.

This converges to the $k$-th smallest element in $O(n \log(max - min))$ time. The logarithm comes from halving the value range.