# 04.二维数组中的查找

### 一、 题目

在一个 n \* m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 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 = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

注意：本题与主站 240 题相同：<https://leetcode-cn.com/problems/search-a-2d-matrix-ii/>

链接：<https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof>

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 二、 解法

#### 2.1 从右上角开始

```
func findNumberIn2DArrayA(_ matrix: [[Int]], _ target: Int) -> Bool {
    guard matrix.isEmpty == false, let first = matrix.first, first.isEmpty == false else {
        return false
    }
    var x = first.count - 1, y = 0
    
    while y < matrix.count {
        let line = matrix[y]
        let lineFinal = line[line.count - 1]
        
        if lineFinal >= target {
            while x >= 0 {
                if line[x] != target {
                    x -= 1
                }
                else {
                    return true
                }
            }
        }
        
        y += 1
        x = first.count - 1
    }
    
    return false
}
```

#### 2.2 从右上角开始优化

```
func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {
    guard matrix.isEmpty == false, let first = matrix.first, first.isEmpty == false else {
        return false
    }
    var x = first.count - 1, y = 0
    
    while y < matrix.count, x >= 0 {
        let value = matrix[y][x]
        if value > target { x -= 1 }
        else if value < target { y += 1 }
        else { return true }
    }
    
    return false
}
```

#### 2.3 从左下角

```
func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {
    guard matrix.isEmpty == false, let first = matrix.first, first.isEmpty == false else {
        return false
    }
    var x = 0, y = matrix.count - 1
    
    while x < first.count, y >= 0 {
        let value = matrix[y][x]
        if value > target { y -= 1 }
        else if value < target { x += 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://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/04.-er-wei-shu-zu-zhong-de-cha-zhao.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.