# 240. Search a 2D Matrix II

{% embed url="<https://leetcode.com/problems/search-a-2d-matrix-ii/>" %}

### 自右上而左下 Binary Search <a href="#ti-jie-zi-you-shang-er-zuo-xia" id="ti-jie-zi-you-shang-er-zuo-xia"></a>

{% content-ref url="../74.-search-a-2d-matrix" %}
[74.-search-a-2d-matrix](https://xuqiangwen1994.gitbook.io/practice/74.-search-a-2d-matrix)
{% endcontent-ref %}

1. 跟 Q74 不同，这次的升序只在各行和各列内部，无法再把 matrix 当作一维`sorted array`处理。
2. 如果从左上角开始搜索，由于元素升序为自左向右和自上而下，因此如果 target 大于当前搜索元素时还有两个方向需要搜索，不太合适。
3. 如果从右上角开始搜索，当前行与当前列连接起来就是一个`sorted array`，这样就可以利用二分法的思路，通过比较当前元素与`target` ，排除一列或者一行元素（大于当前元素则排除当前行，小于当前元素则排除当前列，由矩阵特点可知）。

```python
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]: return False
        m, n = len(matrix), len(matrix[0])
        if matrix[m-1][n-1] < target or matrix[0][0] > target: return False
        row, column = 0, n-1
        while row < m and column >= 0:
            cur = matrix[row][column]
            #print(cur)
            if cur == target: return True
            elif cur > target: column -= 1
            else: row +=1
                
        return False
```
