Binary search doesn't have to search indices. You can search the value space. Here, the smallest element is and the largest is .
For any value , you can count how many matrix elements are by walking from the bottom-left corner. If the count is , search higher values. If , search lower values.
This converges to the -th smallest element in time. The logarithm comes from halving the value range.