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.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

分析

1. 题目要求

给出一个m * n矩阵，该矩阵每一行都是从小到大排列，每一列也是如此。找出该矩阵中是否含有给出的目标数。

2. 求解思路

最简单的方法，可以从左到右，从上到下依次遍历整个矩阵看是否含有目标数，但时间复杂度为 O(mn)。
由于已经排好序了，我们可以依次将每一行的第一个元素和目标数作比较，找出目标数可能在的行数。

再将该行的每一个元素和目标数作比较，看是否含有目标数。时间复杂度为 O(m + n)。
其实这个与一维已排序数组查找目标数差不多，可以使用二分查找的方法来求解。

先使用二分查找(每次与中间的那一行作比较)，找到目标数可能在的那一行。

再继续对目标行使用二分查找，看是否含有目标数。时间复杂度为 O( log(mn) )。

3. 代码如下

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int a = 0;
        int b = m - 1;
        int index = (b + a) / 2;
        while (b >= a) {
            if (matrix[index][0] <= target && matrix[index][n-1] >= target) {
                for (int i = 0; i < n; i++) {
                    if (matrix[index][i] == target) return true;
                }
                int c = 0, d = n - 1;
                int mid = (c + d) / 2;
                while (d >= c) {
                    if (matrix[index][mid] == target) {
                        return true;
                    } else if (matrix[index][mid] < target) {
                        c = mid + 1;
                        mid = (c + d) / 2;
                    } else {
                        d = mid - 1;
                        mid = (c + d) / 2;
                    }
                }
                return false;
            } else if (matrix[index][0] > target) {
                b = index - 1;
                index = (b + a) / 2;
            } else if (matrix[index][n-1] < target) {
                a = index + 1;
                index = (b + a) / 2;
            }
        }
        return false;
    }
};