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;

    }

};