# 0240. 搜索二维矩阵 II

### 题目地址(240. 搜索二维矩阵 II)

<https://leetcode-cn.com/problems/search-a-2d-matrix-ii/>

### 题目描述

```

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:

现有矩阵 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。

```

### 前置知识

* 数组

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

符合直觉的做法是两层循环遍历，时间复杂度是 O(m \* n), 有没有时间复杂度更好的做法呢？ 答案是有，那就是充分运用矩阵的特性（横向纵向都递增）， 我们可以从角落（左下或者右上）开始遍历，这样时间复杂度是 O(m + n).

![](https://p.ipic.vip/yaajgz.jpg)

其中蓝色代表我们选择的起点元素， 红色代表目标元素。

### 关键点解析

* 从角落开始遍历，利用递增的特性简化时间复杂

### 代码

代码支持：JavaScript, Python3

JavaScript Code:

```js
/*
 * @lc app=leetcode id=240 lang=javascript
 *
 * [240] Search a 2D Matrix II
 *
 * https://leetcode.com/problems/search-a-2d-matrix-ii/description/
 *
 *
 */
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  if (!matrix || matrix.length === 0) return false;

  let colIndex = 0;
  let rowIndex = matrix.length - 1;
  while (rowIndex > 0 && target < matrix[rowIndex][colIndex]) {
    rowIndex--;
  }

  while (colIndex < matrix[0].length) {
    if (target === matrix[rowIndex][colIndex]) return true;
    if (target > matrix[rowIndex][colIndex]) {
      colIndex++;
    } else if (rowIndex > 0) {
      rowIndex--;
    } else {
      return false;
    }
  }

  return false;
};
```

Python Code:

```python
class Solution:
    def searchMatrix(self, matrix, target):
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        i = m - 1
        j = 0

        while i >= 0 and j < n:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        return False
```

**复杂度分析**

* 时间复杂度：$O(M + N)$
* 空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/j14g18.jpg)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/240.search-a-2-d-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.