题目地址：

https://leetcode.com/problems/search-a-2d-matrix/

给定一个$m\times n$的矩阵$A$，每行单调上升，并且每行的末项都小于下一行的首项。另给定一个数，问这个数是否在矩阵里。

思路是二分法，可以将整个矩阵看成一整条单调上升的数组，只需要建立一个一维到二维的映射就可以了。若$A[m][n]$是$m$行$n$列，将每行从第$0$行到第$m-1$行按顺序前后拼起来成为一个长数组，那么长数组的下标$t$对应在矩阵里的下标为$(t/n,t\%n)$。接下来只要二分就行了。代码如下：

class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& A, int t) {
    int n = A[0].size();
    int l = 0, r = (int)A.size() * n - 1;
    if (l > r) return false;
    while (l < r) {
      int mid = l + (r - l >> 1);
      int x = mid / n, y = mid % n;
      if (A[x][y] >= t) r = mid;
      else l = mid + 1;
    }

    return A[l / n][l % n] == t;
  }
};

时间复杂度为$O(\log (nm))$，空间$O(1)$。