74.Search a 2D Matrix

Tags: Binary Search Medium

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

---

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

---

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

        return false;
    }
};

前半部分查找是找最后一个不大于目标值的数，实际上就是upper_bound找到位置的前一个数，主要是注意如果找到的位置是首迭代器，那么就在当前行即可。剩下的就是在对应行内的二分查找。这题细节较多，比如得判断是否m == 0, n == 0等。

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

也可以使用一次二分查找法，如果我们按S型遍历该二维数组，可以得到一个有序的一维数组，只需要用一次二分查找法，而关键就在于坐标的转换，如何把二维坐标和一维坐标转换是关键点，把一个长度为n的一维数组转化为 m*n 的二维数组 (m*n = n)后，那么原一维数组中下标为i的元素将出现在二维数组中的[i/n][i%n] 的位置