### Solution

#### Analysis

Since the matrix is sorted in two directions, using binary search to find the kth smallest is an intuitive method. Since we are searching for the number, so the searching space should be the space ranging from the smallest to the biggest number in the matrix.

Note that the index here cannot be used to form the searching space since it's not linear to the numbers in the matrix, whose order lies in two directions unlike the index from 0 to size(size-1).

Take [[1,4],[3,5]] 2 as an example. If we use the index range as the searching space,

`l=0, r=3, m=(0+3)/2=1`

in the first round and then the numbers smaller than or equal to its number,`matrix[m/size][m%size]=matrix[1/2][1%2]=matrix[0][1]=4,`

are 3 (1, 4 and 3 respectively) and then we will set r=m=1. Just now we have eliminated the potential answer number 3, whose index should be 2 matrix[2/2][2%2]=matrix[1][0]. All of these are because the index sequence is not linear to the matrix numbers whose order lies in two directions.

#### Details

- Start with half of the smallest and biggest of the matrix, and then count how many numbers are smaller than or equal to it row by row;
- K directly becomes the comparison determining which direction we will go in the next round, left part or the right part;
- Keep the answer number within the range [l, r] in each round.

The time complexity will be O(nlognlogm) while n is the number of rows in the matrix and m is the gap between the smallest and the biggest number in the matrix.

```
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
{
int size = matrix.size(), l = matrix[0][0], r = matrix[size-1][size-1];
while(l < r)
{
int smaller = 0, m = l+((r-l)>>1);
for(int i = 0; i < size; ++i)
smaller += upper_bound(matrix[i].begin(), matrix[i].end(), m)-matrix[i].begin();
smaller<k? l=m+1 : r=m;
}
return r;
}
};
```

Always welcome new ideas and `practical`

tricks, just leave them in the comments!