问题：
给定一个二维数组，每一行，每一列，都是升序排列的。
但A[0][1]不一定<A[1][0]（右上↗?元素不一定<左下元素↙?，但左上↖?一定<右下↘?）
求整个二维素组中第K个大的元素值。
Example: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13. Note: You may assume k is always valid, 1 ≤ k ≤ n2.
解法：二分查找(Binary Search)
最小值l：A[0][0]
最大值r：A[n-1][n-1]
找到第一个小的m，使得count(比m小的数)=k
轮询每行，由于已排序，找到比m小的index=每行count(<m的数)
找到比m小的index -> upper_bound(row, m)，找到row数组中第一个>m的数的index。
代码参考：
1 class Solution { 2 public: 3 int kthSmallest(vector<vector<int>>& matrix, int k) { 4 int n = matrix.size(); 5 int l = matrix[0][0], r = matrix[n-1][n-1]; 6 while(l<r) { 7 int m = l+(r-l)/2; 8 int cout = 0; 9 for(auto row:matrix) { 10 int idx = upper_bound(row.begin(), row.end(), m) - row.begin(); 11 cout += idx; 12 } 13 if(cout >= k) {//find the first m -> cout>=k 14 r = m; 15 } else { 16 l = m+1; 17 } 18 } 19 return l; 20 } 21 };
378. Kth Smallest Element in a Sorted Matrix
原文：https://www.cnblogs.com/habibah-chang/p/13496000.html