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

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

解法一：二分

参考官方题解的方法三，非常精妙的二分

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n=len(matrix)
        #判断不大于mid的数是否超过k个
        def check(mid):
            i=n-1
            j=0
            num =0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    j += 1
                    num += i+1
                else:
                    i -=1
            return num >=k
        l=matrix[0][0]
        r = matrix[-1][-1]
        while l < r:
            mid = l+ (r-l)//2
            #不大于mid的数不少于k，说明最终答案x不大于mid
            if check(mid):
                r = mid
            #数量少于k，说明最终答案x大于mid
            else:
                l = mid+1
            print(l,r)
        return l