74. 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

思路

从题目可见，这是一个严格递增的二维数组，所以，可以将其展开成以为一维数组，然后进行二分法查找。

一维数组中 index 在二维数组中对应第 index/n 行，index%n 列。

c++11

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

上述代码运行一直没出，但是提交的话出现如下错误

Runtime Error Message: Line 12: division by zero

代码中n确实肯定不为0，但是可能会出现溢出的情况，溢出反转可能会使得其为0。加个判断就ok。

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

这样就accept了。

注：

在计算mid = (low+high)/2 的时候，(low + high) 可能溢出。

正确的写法应该是：int mid = low + (high - low)/2 。

溢出

1、示例

测试一下：

#include <iostream>
using namespace std;

int main() {
    int a = 2147483647;
    int b = a + 1;
    cout << "a = " << a << endl;
    cout << "b = " << b << endl;
}

编译

g++ test.cc -o test

运行结果

▶ ./test
a = 2147483647
b = -2147483648

2、内置类型对整数常量的限制

#include <limits.h>

列表如下：