> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/binary-search/240.-search-a-2d-matrix-ii.md).

# 240. Search a 2D Matrix II

\# Medium

{% hint style="success" %}
find the fisrt position in a row bigger than target, then throw corresponded columns

consider edge case
{% endhint %}

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-M6vGzbxvPi_aaIx0CUY%2F-M6vMxtfDZTPtHWtqbxf%2FWechatIMG630.png?alt=media\&token=814d86ba-257e-4d7e-ada1-37321ec48c68)

> matrix is `m` rows and `n` columns, `m * n`

### Solution 1:

check from first to last row, find the first position in a row bigger than target, then throw one row or a few columns with one row

do search insertion position in each row

time complexity: $$O(m\*lg(n))$$ 

### Soultion 2:

check from right top or left bottom element, every time throw one column or row

Time complexity: $$O(m+n)$$ 

{% tabs %}
{% tab title="Java" %}

```java
// Some code
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length - 1, col = 0;
        while(row >= 0 & col <= matrix[0].length - 1) {
            if(matrix[row][col] == target)
                return true;
            else if(matrix[row][col] > target)
                row --;
            else
                col ++;
        }
        
        return false;
    }
}
```

{% endtab %}
{% endtabs %}