Finding the k-th small element of ordered matrix (dichotomy idea)

Their thinking
Two points search , Convert two dimensions to one dimension ,check The function is used to solve less than or equal to target The number of elements is the same as k The relationship between

Code

class Solution {
    
public:
    // Statistical satisfaction less than target Number of array elements , exceed k return true, Not more than k return false
    bool check(vector<vector<int>>& matrix, int cnt,int target,int k){
    
        int num = 0;
        int i = cnt-1;
        int j = 0;
        while(i>=0 && j<cnt){
    // Start at the lower left corner of the matrix , And statistics of the second j Column to the first i Number of elements in the row 
            if(matrix[i][j]<=target){
    // Find each column <=target Element location of 
                j++;
                num+=i+1;
            }else{
    
                i--;
            }
        }
        return num>=k;
    }


    // Two points search 
    int kthSmallest(vector<vector<int>>& matrix, int k) {
    
        int cnt = matrix.size();
        int left = matrix[0][0];
        int right = matrix[cnt-1][cnt-1];
        while(left<right){
    // Find the leftmost boundary 
            int mid = left + (right-left)/2;
            if(check(matrix,cnt,mid,k)){
    
                right = mid;
            }else{
    
                left = mid+1;
            }
        }
        return left;
    }
};