1. 074

set-matrix-zeroes

2. 算法

O(lg(nm))

http://www.cnblogs.com/grandyang/p/4323301.html

• S形查找
• m*n=n的一维数组，
• 下标i的元素在二维数组的位置：[i/n][i%n]

3. 代码

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