题目描述： 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例： matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。
提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。 方法1：参考官方解答 主要思路： （1）数组的每一行是升序，每一列是升序，则数组整体是从左上方到右下方升序，既小值集中在左上部分，大值集中在右下部分； （2）由这个有序性，考虑使用二分查找，这里使用数组中的最小值left=matrix[0][0]，数组中的最大值right=matrix[n-1][n-1]，来构建中间值mid=left+((right-left)>>1)，来分割整个数组，将整个数组分为左上和右下两部分，然后判断左上部分的元素的个数和 k 的关系，调整left 或right，使left和right逐渐的夹逼到中间的第k个值； （3）考虑到数组的有序性，从左下角开始对数组进行分割，并统计其左上部分的元素数量，注意这里将等于mid 的值划分到左上部分了；
class Solution { public: bool check(vector<vector<int>>&matrix,int k,int mid,int n){ //i，j 的赋值保证时从左下开始遍历分割数组的 int i=n-1; int j=0; int num=0;//统计左上部分的元素的个数，既小于等于mid 的元素个数 while(i>=0&&j<n){//终止条件，既超出了数组范围 if(matrix[i][j]<=mid){ num+=i+1;//更新左上元素的数量 ++j;//更新列 } else{ --i;//更新行 } } return num>=k;//判断第k个值是否在左上部分 } int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); int left=matrix[0][0];//最小值 int right=matrix[n-1][n-1];//最大值 int mid=0; while(left<right){//终止条件，既夹逼到了第k个值 mid=left+((right-left)>>1);//当前中间值//注意移位运算符的使用，比+运算符级别低，加括号 if(check(matrix,k,mid,n)){ right=mid;//若第k个值在左上部分 } else{ left=mid+1;//若第k个值在右下部分 } } return left;//返回夹逼到的值//这里使用return right;是一样的结果 } };