# Search a 2D Matrix II

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

**Example:**

Consider the following 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]
]
```

Given target = `5`, return `true`.

Given target = `20`, return `false`.

分析

和Search a 2D Matrix I的区别是 1的pre row【-1】都< 下面的row【0】。

二分思想，把Matrix分成四份，每次>target, 去掉最后一块，>target,去掉第一块，另外三块做递归。 参数用左上和右下坐标代表一块矩形

**这里注意 i<<1 得到的是整数和下限！！！！**

```

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
        n,m = len(matrix),len(matrix[0])
        def helper(upperLeft,lowerRight):
            x1,y1 = upperLeft
            x2,y2 = lowerRight
            if x1 > x2 or y1 > y2 or x2 >= n or y2 >= m:
                return False
            if x1==x2 and y1==y2:
                return matrix[x1][y1] == target
            x = (x1+x2)>>1
            y = (y1+y2)>>1
                       
            if matrix[x][y] < target:                
                return helper((x+1,y1),(x2,y)) or helper((x1,y+1),(x,y2)) or helper((x+1,y+1),lowerRight)
            elif matrix[x][y] > target:
                 return helper(upperLeft,(x,y)) or helper((x+1,y1),(x2,y)) or helper((x1,y+1),(x,y2))
            else:
                return True
            
        return helper((0,0),(n-1,m-1))
                
            
        
```

第二种做法，直接起始点从右上角开始，或者向下或者向左。

```
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
        n,m = len(matrix),len(matrix[0])
        i,j=0,m-1
        while i < n and j >=0:
            if matrix[i][j] > target:
                j -= 1
            elif matrix[i][j] < target:
                i += 1
            else:
                return True
        return False
            
            
        
                
            
        
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l2er-fen-cha-zhao/search-a-2d-matrix-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.