【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素

class Solution {
public:
  int kthSmallest(vector<vector<int>>& matrix, int k) {
    m_c = matrix.size();
    int left = matrix.front().front()-1, r = matrix.back().back();
    while (r - left > 1)
    {
      const auto mid = left + (r - left) / 2;
      if (Cnt(matrix, mid) >= k)
      {
        r = mid;
      }
      else
      {
        left = mid;
      }
    }
    return r;
  }
  int Cnt(const vector<vector<int>>& matrix, int x)
  {
    int iCnt = 0;
    for (int r = m_c - 1,right=0; r >= 0; r--)
    {
      for (; (right < m_c) && (matrix[r][right] <= x); right++);
      iCnt += right;
    }
    return iCnt;
  }
  int m_c;
};
# 测试用例
```cpp
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<vector<int>> matrix;
  int k;
  {
    Solution slu;
    matrix = { {1,5,9},{10,11,13},{12,13,15} }, k = 8;
    auto res = slu.kthSmallest(matrix, k);
    Assert(13, res);
  }
  {
    Solution slu;
    matrix = { {-5} }, k = 1;
    auto res = slu.kthSmallest(matrix, k);
    Assert(-5, res);
  }
}