###### tags: `Leetcode` `medium` `array` `binary search` `python` `Top 100 Liked Questions`

# 74. Search a 2D Matrix

## [題目連結:] https://leetcode.com/problems/search-a-2d-matrix/

## 題目:
Write an efficient algorithm that searches for a value ```target``` in an ```m x n``` integer matrix ```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.


#### [圖片來源:] https://leetcode.com/problems/search-a-2d-matrix/

## 解題想法:
* 題目給的矩陣中:
* 矩陣中的數字每一個row由左到右已經排序過(小至大)。
* 每一個row的第一個數字一定比上一個row最後一個數字還要大(example1: 10>7)。

* Solution:
* 因為相當於行列都排序過
* 先對第一行做二分法，找target出現的列
* 再對該列做二分法，找target出現的最終位置

## Python:

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        head = 0
        tail = len(matrix)-1
        #對第一行做二分找出現的列
        while head<=tail:
            mid = (head+tail)//2
            if matrix[mid][0]==target:
                return True
            elif matrix[mid][0]<target:
                head = mid+1
            else:
                tail = mid-1
        pos = head-1
        #再對該列做二分找位置
        row_head = 0
        row_tail = len(matrix[0])-1
        while row_head<=row_tail:
            mid = (row_head+row_tail)//2
            if matrix[pos][mid]==target:
                return True
            elif matrix[pos][mid]<target:
                row_head = mid+1
            else:
                row_tail = mid-1
        return False
        
result =Solution()
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 13
ans = result.searchMatrix(matrix,target)
print(ans)