74. 搜索二维矩阵

74. 搜索二维矩阵 - 力扣（LeetCode）

class Solution {
	struct Index {
		int Row, Col;
	};
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		auto convert = [&](int Flat) -> Index {
			int RowSize = matrix[0].size();
			int Row = Flat / RowSize;
			int Col = Flat % RowSize;
			return { Row, Col };
		};

		int Left = 0;
		int Right = matrix.size() * matrix[0].size() - 1;
		while (Left <= Right) {
			int Mid = (Left + Right) / 2;
			Index Idx = convert(Mid);
			if (matrix[Idx.Row][Idx.Col] < target)
				Left = Mid + 1;
			else if (matrix[Idx.Row][Idx.Col] > target)
				Right = Mid - 1;
			else
				return true;
		}
		return false;
	}
};

这题没什么好说的，三分类的朴素二分，注意边界均要有效、更新指针时需要根据方向进行 Mid + 1 或 Mid - 1 的偏移即可。

二刷

class Solution {
public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int Stride = matrix.front().size();
    int Size = Stride * matrix.size();
    int L = 0, R = Size;
    while (L != R) {
      int M = (L + R) / 2;
      int Row = M / Stride, Col = M % Stride;
      int Val = matrix[Row][Col];
      if (Val == target)
        return true;
      if (Val < target)
        L = M + 1;
      else
        R = M;
    }
    return false;
  }
};

没什么好说的。

三刷

class Solution {
public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int Height = matrix.size();
    int Width = matrix.front().size();
    int L = 0, R = Height * Width;
    while (L != R) {
      int M = L + (R - L) / 2;
      int Row = M / Width;
      int Col = M % Width;
      if (matrix[Row][Col] == target)
        return true;

      if (matrix[Row][Col] < target)
        L = M + 1;
      else
        R = M;
    }
    return false;
  }
};