378. 有序矩阵中第 K 小的元素

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
二分法，不同于常规的二分法使用下标进行缩小范围，改题目由于是局部有序，因此只能用数值以不断缩减范围，初始化left=nums[0][0],right=nums[len-1][len-1]（一个最大值，一个最小值），然后计算mid的值，通过O(n)的“中分线算法”计算不大于mid的数有几个——计为sum，可以理解为mid这个数在所有数字里的最大排名就是sum(说最大是因为可能有并列的)，然后如果sum大于目标值k，说明[0,mid]的数过多，需要让mid更小，于是令right=mid，反之就是太多，令left=mid+1(为何+1，前期还没什么区别，后期不+1就会死循环，具体还不知道)，总之就是mid小了就让他大点，大了就让他小点，直到left=right的时候，mid就是最终答案x了。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];
        while(left<right){
            int mid = left + ( (right-left)>>1 );
            if(left_enough(matrix,n,k,mid)){
                right = mid ;
            }else{
                left = mid +1;
            }
        }
        return left;
    }

    public boolean left_enough(int[][] matrix, int n, int k, int mid){
        //从左下角开始，寻找mid分界线,分界线每一次向右都说明左上列是完全ok的，例如(n-1,0)右移到(n-1,1)
        //则左上列"(n-1,0)-(0,0)"都是满足if的
        int i = n-1;
        int j = 0;
        int sum = 0; //统计<=mid的数量
        //因为一直向上或者右，所以限制i>0 and j<n
        while(i>=0&&j<n){
            if(matrix[i][j]<=mid){
                j++;
                sum += (i+1);//指针刚刚右移，左上列都是<=的
            }else{//
                i--;  
            }
        }
        return sum >= k ;     
    }
}