```
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
if(n == 0) return -1;
int minval = matrix[0][0] , maxval = matrix[n - 1][n - 1], mid;
while(minval < maxval)
{
mid = minval + ((maxval - minval) >> 1);//find the middle value of the range between maxval and minval
int count = 0, j = n - 1;
for(int i = 0; i < n && matrix[i][0] <= mid; i++)//count how many number of elements in the matrix less than middle value.
{
while(j >= 0 && matrix[i][j] > mid) j--;
count += j + 1;
}
if(count < k)
minval = mid + 1;
else
maxval = mid;
}
return minval;
}
};
```

just think this matrix as a range of [minval maxval]. Every time we find the middle value in this range, and count how many number in the matrix less than the middle value.Finally, we renew the range base on count number.