378. Kth Smallest Element in a S

由于二维数组行和列都是有序的，所以左上角的元素是最小的，右下角的元素是最大的。
我们从这两个元素开始，使用二分法查找，取这两个元素的中间值，看看数组里有多少个元素小于等于它，如果少于k就在后半部分里找，如果多于k就从前半部分里找。

int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
    int n = matrixRowSize;
    int low = matrix[0][0];
    int high = matrix[n-1][n-1];
    int mid;
    int i,j;
    int count;
    while(low < high)
    {
        j = n - 1;
        mid = low + (high - low)/2;
        count = 0;
        for(i = 0; i < n; i++)
        {
            while(j >= 0 && matrix[i][j] > mid)
                j--;
            
            count += j + 1;
        }
        
        if(count < k)
            low = mid + 1;
        else
            high = mid;
    }
    
    return low;
}