# Search in 2D array

### 1. Link

{% embed url="<https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking>" %}

### 2. 描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。\[  \[1,2,8,9],\
&#x20; \[2,4,9,12],\
&#x20; \[4,7,10,13],\
&#x20; \[6,8,11,15]\
]

给定 target = 7，返回 true。

给定 target = 3，返回 false。<br>

### 示例1

输入：

```
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
```

复制返回值：

```
true
```

复制说明：

```
存在7，返回true
```

### 示例2

输入：

```
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
```

复制返回值：

```
false
```

复制说明：

```
不存在3，返回false
```

### 3. 思路

1. search from the upper left corner, since element < current element on the left,  element > current element on the bottom
2. case 1:  if current element < target -> row += 1
3. case 2:  if current element > target -> column -= 1
4. Otherwise, return true if target is found

### 4. Coding

```
class Solution:
    # array 二维列表
    def Find(self, target, array):
        #
        #input: target int, 2D array,  output: boolean 
        # idea: binary search
        # search from upper left corner
        # since element < cur on the left, >cur on the bottom, so
        # check current element:
        #  case 1: if current clement < target ->search bottom
        # case 2: if current elemtn > target -> search left side
        if not array or not array[0] or target == None:
            return False
        
        r, c = 0, len(array[0])-1
        while c >=0 and r < len(array):
            if array[r][c] <target:
                r += 1
            elif array[r][c] >target:
                c -= 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://wenkangwei.gitbook.io/leetcode-notes/datastructure/searching/search-in-2d-array.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.