leetcode 在有序矩阵中查找某个数，第k小数 （二分法）

240. Search a 2D Matrix II

题目地址

https://leetcode.com/problems/search-a-2d-matrix-ii/

查找特定的某个数，主要是根据矩阵有序，采用二分法缩小矩阵的搜索范围

378. Kth Smallest Element in a Sorted Matrix

题目地址

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

查找第k小数，主要是对数采用二分法。对某个数，在矩阵中查找小于等于该数的个数，最后把数定下来，然后判断

ac代码

class Solution {
public:

    // 小于等于num的数的个数
    int cntlow(vector<vector<int>>& matrix, int m, int n, int num)
    {
        int cnt = 0;

        int x = n-1;
        int y = 0;

        while(x >= 0 && y <= m-1)
        {
            while( x >= 0 && matrix[y][x] > num)
                x--;
            if(x < 0)
                break;
            cnt += x - 0 + 1; // 每一行小于等于num的数的个数
            y ++; // 下一行
        }

        return cnt;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        if(m == 0)
            return 0;
        int n = matrix[0].size();
        if(n == 0)
            return false;

        int minVal = matrix[0][0];
        int maxVal = matrix[m-1][n-1];
        /* 定位到某个数 minVal 或者maxVal minVal <= maxVal 最后退出的时候，minVal 和 maxVak 一定是matrix中的数 */
        while(minVal < maxVal - 1)
        {
            int mid = (maxVal - minVal) / 2 + minVal;
            int cnt = cntlow(matrix,m,n,mid);
            if(cnt < k){
                minVal = mid;
            }else{
                maxVal = mid;
            }
        }

        if(cntlow(matrix,m,n,minVal) >= k)
            return minVal;
        return maxVal;
    }
};

ac参考
菁小妖的博客
http://blog.sina.com.cn/s/blog_a6bd98c90102x19a.html