问题

如题。矩阵每行、每列都是非递减序。

算法: 值域二分

二分分为索引二分和值域二分。索引二分适合已知值的信息，求索引；值域二分适合已知索引的信息，求值。

这道题为什么能够想到用值域二分？

1. 值域是确定的
2. 有索引信息（第K小），求值的信息

时间复杂度

$O(NlogL)$, L为值域大小

代码

class Solution {
public:
    int m, n;
    int search(vector<vector<int>> &matrix, int mid){
        int ans = 0;
        for(int i = 0, j = n-1; i < m && j >= 0; ){
            if(matrix[i][j] <= mid){
                ans += j+1;
                i ++;
            }else{
                j --;
            }
        }
        return ans;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        m = matrix.size(), n = matrix[0].size();
        int l = matrix[0][0], r = matrix[m-1][n-1];
        while(l < r){
            int mid = l + r >> 1;
            // cout<<mid<<' '<<search(matrix,mid)<<endl;
            if(search(matrix, mid) >= k) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};