搜索二维矩阵

题面

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出： true

示例 2：

输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出： false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

分析

• 可以先根据第一列，来查找 target 在哪一行

• 然后在这一行中查找 target 的位置，如果找到就返回 true；

• 因此这是两次二分查找过程

• 代码实现

  class Solution {
  public:
      bool searchMatrix(vector<vector<int>>& matrix, int target) {
          int left = 0, right = matrix.size() - 1, mid = 0;
          while (left <= matrix.size() - 1 && right >= 0 && left <= right) {
              mid = left + (right - left) / 2;
              if (matrix[mid][0] < target) {
                  left = mid + 1;
              } else if (matrix[mid][0] > target) {
                  right = mid - 1;
              } else {
                  return true;
              }
          }
          int row = matrix[mid][0] < target ? mid : max(mid - 1, 0);
          left = 0;
          right = matrix[row].size() - 1;
          while (left <= matrix[row].size() - 1 && right >= 0 && left <= right) {
              mid = left + (right - left) / 2;
              if (matrix[row][mid] < target) {
                  left = mid + 1;
              } else if (matrix[row][mid] > target) {
                  right = mid - 1;
              } else {
                  return true;
              }
          }
          return false;
      }
  };

• 另一种更简单的做法是，由于矩阵的每一行是递增的，且每行的第一个数大于前一行的最后一个数，如果把矩阵每一行拼在一起，可以得到一个递增数，那么可以直接在这个数组上去二分查找

• 代码实现时，并不需要真正拼成一个长度为 mn 的数组，而是将 i 转换为矩阵中的行号和列号，一般地

  $$a[i] = \text{matrix}[\lfloor i/n \rfloor][i \bmod n]$$

• 其中，a 是假设的一维数组，i 是假设的一维数组重点下标

• 代码实现

  class Solution {
  public:
      bool searchMatrix(vector<vector<int>>& matrix, int target) {
          int m = matrix.size(), n = matrix[0].size();
          int left = -1, right = m * n;
          while (left + 1 < right) {
              int mid = left + (right - left) / 2;
              int x = matrix[mid / n][mid % n];
              if (x == target) {
                  return true;
              }
              (x < target ? left : right) = mid;
          }
          return false;
      }
  };

• 也可以直接利用排除法，从右上角查找 target

  • 如果右上角小于 target，意味着这一排的数都小于该数，那么直接排除
  • 如果右上角大于 target，意味着这一列的数都大于该数，那么直接排除
  • 直至右上角元素等于 target，找到；否则最后遍历完后没找到

• 代码实现

  class Solution {
  public:
      bool searchMatrix(vector<vector<int>>& matrix, int target) {
          int m = matrix.size(), n = matrix[0].size();
          int i = 0, j = n - 1;
          while (i < m && j >= 0) { // 还有剩余元素
              if (matrix[i][j] == target) {
                  return true; // 找到 target
              }
              if (matrix[i][j] < target) {
                  i++; // 这一行剩余元素全部小于 target，排除
              } else {
                  j--; // 这一列剩余元素全部大于 target，排除
              }
          }
          return false;
      }
  };