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. 从头到尾遍历, 没有算法可言. 时间复杂度 O(m*n)
2. 先遍历行的最后个元素, 可以确定要search的行. 然后再遍历此行, 时间复杂度 O(m + n)
3. 把整个martrix 看成一个首尾相连的二维数组, 然后使用二分法. 时间复杂度 O(log(m*n))
4. 对行首元素使用二分法确定要search的行, 然后再对此行使用二分法. 时间复杂度 O(logm+logn)

本题是使用第4种算法.

Java:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if (row == 0) return false;
        int column = matrix[0].length;
        if (column == 0) return false;
        int left = 0;
        int right = row - 1;
        int mid = 0;
        int comp = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            comp = matrix[mid][0];
            if (comp < target) left = mid + 1;
            else if (comp > target) right = mid - 1;
            else return true;
        }
        if (right < 0) return false;
        int rowIndex = right;
        left = 0;
        right = column - 1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            comp = matrix[rowIndex][mid];
            if (comp < target) left = mid + 1;
            else if (comp > target) right = mid - 1;
            else return true;
        }
        return false;
    }
}

C++:

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

Python:

class Solution:
    # @param matrix, a list of lists of integers
    # @param target, an integer
    # @return a boolean
    def searchMatrix(self, matrix, target):
        row = len(matrix)
        if (row == 0):
            return False
        column = len(matrix[0])
        if (column == 0):
            return False;
        left = 0
        right = row - 1
        rowIndex = 0
        while left <= right:
            mid = left + (right - left) / 2
            comp = matrix[mid][0]
            if (comp > target):
                right = mid - 1
            elif (comp < target):
                left = mid + 1
            else:
                return True
        if (right == -1):
            return False
        print [left, mid, right]
        rowIndex = right
        left = 0
        right = column - 1
        while left <= right:
            mid = left + (right - left) / 2
            comp = matrix[rowIndex][mid]
            if (comp > target):
                right = mid - 1
            elif (comp < target):
                left = mid + 1
            else:
                return True
        return False

本博客所有文章如无特别注明均为原创。作者：Gcaufy
复制或转载请以超链接形式注明转自码疯窝，原文地址 LeetCode 每日一题 — Search a 2D Matrix