LeetCode 74. 搜索二维矩阵

Categories:

Tags:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 74. 搜索二维矩阵

思路分析

解法一：二分查找（推荐）

核心思路：

矩阵每行有序且行首大于上一行行尾，可视为一维有序数组。

通过下标映射 index -> matrix[index / n][index % n] 进行二分查找。

找到返回 true，否则 false。

复杂度分析：

时间复杂度：O(log(mn))，其中 m、n 表示矩阵行列数。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = matrix[mid / n][mid % n];

            if (val == target) {
                return true;
            }
            if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
	m := len(matrix)
	n := len(matrix[0])
	left := 0
	right := m*n - 1

	for left <= right {
		mid := left + (right-left)/2
		val := matrix[mid/n][mid%n]

		if val == target {
			return true
		}
		if val < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return false
}

相似题目

题目	难度	考察点
240. 搜索二维矩阵 II	中等	二分查找
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找
378. 有序矩阵中第 K 小的元素	中等	二分查找
704. 二分查找	简单	二分查找
74. 搜索二维矩阵	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/30863730