378.md

一开始想根据大小规律找一些低于nlog(n)的算法，看来还是naive 将每个矩形格对应的可能最小和最大的index标出来，可以发现能够排除的区域可能只有左上、右下的正方形，用处不大。

最后还是根据解答，写的二分查找，复杂度为O(nlog(n)log(数的大小范围？))

二分还是不大熟，如果left的更新条件跟right一样都是等于mid，那显然死循环 如果判断条件为A，则最后的终止状态是，left=right不满足A，left-1满足A。 right的范围要根据你要找的最终的数来决定，如果是找位置并且有可能找最后一个数之后的位置，注意right的初始化

以上！

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0], right = matrix[n-1][n-1];
        int mid;
        while(left < right){
            mid = (left + right) >> 1;
            int count = 0;
            for(int i = 0; i < n; ++i){
                int ll = 0, rr = n, mm;
                while(ll < rr){
                    mm = (ll + rr) >> 1;
                    if(matrix[i][mm] <= mid) ll = mm + 1;
                    else rr=mm;
                }
                count += ll;
            }
            if(count < k) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};