***Leetcode 378. Kth Smallest Element in a Sorted Matrix

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

非常好的题。

另外从https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85182/My-solution-using-Binary-Search-in-C++

这里也学到一个二分到底是<还是<=的判断方法

Because the loop invariant is left<=Solution<=right. The moment it quits the loop, we also know another condition is true: left>=right.

left<=Solution<=right and left>=right means left==Solution==right.

另外不会死循环是因为，死循环的话mid = r，l<=r所以l = r，这个时候肯定已经跳出循环，所以不会死循环。

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        while (l < r) {
            int mid = (l+r)/2;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                int pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
                //从pos开始 值都是大于等于mid的
                cnt += pos;
            }
            if (cnt < k) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
};