###### tags: `Leetcode` `medium` `array` `binary search` `divide and conquer` `python` `c++` `Top 100 Liked Questions`

# 240. Search a 2D Matrix II

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

## 題目:
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 in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.


* All the integers in each row are sorted in ascending order.
* All the integers in each column are sorted in ascending order.

## 解題想法:
* 此題為，給一matrix，求target是否在此matrix中
* 該matrix: 每行、每列 皆由小到大排序
* 類別同 [74. Search a 2D Matrix](/BPus2qV6QLihxXGNWrfB9A)
* 但不能用P74的方法
* P74是題目設計說:
* 每列第一個數一定比前一列的最後一個數字大
* 所以可以分別對行、列進行binary search，即可找到target

* 此題解:
* 由matrix **右上角** 進行判斷:
* m=len(matrix)
* n=len(matrix[0])
* row=0
* col=n-1
* 若target<matrix[row][col]:
* 小於則向左移動: col-=1
* 大於則向下移動:
* row+=1

## Python:

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])
        if m==0 or n==0:
            return False
        #從右上角開始找 小於向左 大於向下
        row=0
        col=n-1
        while 0<=row<m and 0<=col<n:
            if matrix[row][col]==target:
                return True
            elif target<matrix[row][col]:
                col-=1
            else:
                row+=1
        return False

matrix = [[1,4,7,11,15],
          [2,5,8,12,19],
          [3,6,9,16,22],
          [10,13,14,17,24],
          [18,21,23,26,30]]
target = 20
result= Solution()
ans = result.searchMatrix(matrix,target)
print(ans)

## C++:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(), n=matrix[0].size();
        int row=0, col=n-1;
        while (row<m && 0<=col){
            if (matrix[row][col]==target)
                return true;
            if (target<matrix[row][col])
                col-=1;
            else
                row+=1;
        }
        return false;
    }
};