Kth Smallest Element in a Sorted Matrix

Do not binary-search a flattened index because row-and-column ordering is not globally sorted in that form. Instead binary-search the numeric range from matrix[0][0] to matrix[n-1][n-1]. For a candidate mid, count entries less than or equal to it in O(n): start at bottom-left; if the value is at most mid, every value above it in that column also qualifies, add row+1 and move right; otherwise move up. If count is at least k, the kth smallest is no greater than mid, so move high down; otherwise move low up. The monotonic predicate count(mid) >= k proves binary search validity. Duplicates are naturally counted as separate entries. A min-heap merging rows is another option, O(k log n), useful when k is small. Test k=1, k=n squared, duplicates, negatives, and a one-by-one matrix. Value-range search costs O(n log(max-min)) time and O(1) extra space.