[LeetCode]题解（python）：074-Search a 2D Matrix

---

题目来源

---

https://leetcode.com/problems/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.

---

题意分析

---

Input:  a matrix and a target to query

Output: True or False

Conditions:在矩阵中查找元素，注意矩阵是有序的

---

题目思路

---

先在列二分查找定位哪一列，然后再行二分查找，注意边界条件

PS:其实直接在列查找的时候，发现low-1小于0时，直接返回False就可以了，但是所贴代码可以移植到插入元素的二分排序里面，为了统一就没有改动了。

---

AC代码（Python）

---

__author__ = 'YE'

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m = len(matrix)
        n = len(matrix[0])
        low = 0
        high = m - 1

        while low <= high:
            mid = (low + high) / 2
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] > target:
                high = mid - 1
            else:
                low = mid + 1
        row = low - 1
        if row < 0:
            row = 0

        low = 0
        high = n - 1

        while low <= high:
            mid = (low + high) / 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        return False

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]]
target = 16
print(Solution().searchMatrix(matrix,target))