LeetCode 74: Search a 2D Matrix (Flattened Binary Search)

2026-03-17 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 74Binary SearchMatrixInterview

Today we solve LeetCode 74 - Search a 2D Matrix.

Source: https://leetcode.com/problems/search-a-2d-matrix/

LeetCode 74 flattened index to matrix coordinate mapping diagram

English

Problem Summary

You are given an m x n matrix where each row is sorted in ascending order, and the first element of each row is larger than the last element of the previous row. Determine whether a target exists in the matrix.

Key Insight

The whole matrix behaves like one globally sorted array of length m*n. We can binary search on this virtual array and map an index mid back to matrix coordinates by:

row = mid / n, col = mid % n.

Brute Force and Limitations

Brute force scans every cell in O(m*n). It works but misses the sorted structure, so it is slower than necessary.

Optimal Algorithm Steps

1) Let left = 0, right = m*n - 1.
2) While left <= right, compute mid.
3) Map mid to (row, col) and read value = matrix[row][col].
4) If value == target, return true.
5) If value < target, move left to mid + 1; else move right to mid - 1.
6) If loop ends, return false.

Complexity Analysis

Time: O(log(m*n)).
Space: O(1).

Common Pitfalls

- Forgetting empty-matrix guard.
- Wrong index mapping (row = mid / n, col = mid % n).
- Using left < right with unsuitable updates and skipping final candidate.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;

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

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

        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1

    for left <= right {
        mid := left + (right-left)/2
        row, col := mid/n, mid%n
        value := matrix[row][col]

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

    return false
}

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = m * n - 1;

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

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

        return false;
    }
};

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1

        while left <= right:
            mid = left + (right - left) // 2
            row, col = divmod(mid, n)
            value = matrix[row][col]

            if value == target:
                return True
            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

var searchMatrix = function(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;

  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const row = Math.floor(mid / n);
    const col = mid % n;
    const value = matrix[row][col];

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

  return false;
};

中文

题目概述

给定一个 m x n 矩阵：每行递增，且每一行的首元素都大于上一行的末元素。判断目标值 target 是否存在于矩阵中。

核心思路

把整个矩阵看成一个长度为 m*n 的有序一维数组，然后进行二分查找。通过下标映射回二维坐标：

row = mid / n，col = mid % n。

暴力解法与不足

暴力法逐个元素扫描，时间复杂度 O(m*n)。虽然可行，但没有利用“整体有序”的结构特性。

最优算法步骤

1）初始化 left = 0，right = m*n - 1。
2）循环中取 mid。
3）计算二维位置 (row, col) 并读取当前值。
4）若等于 target，返回 true。
5）若当前值小于目标，左边界右移；否则右边界左移。
6）循环结束仍未命中则返回 false。

复杂度分析

时间复杂度：O(log(m*n))。
空间复杂度：O(1)。

常见陷阱

- 忘记处理空矩阵/空行。
- 下标映射公式写错导致越界或读错元素。
- 二分边界更新不严谨，漏掉最后一个候选值。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;

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

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

        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1

    for left <= right {
        mid := left + (right-left)/2
        row, col := mid/n, mid%n
        value := matrix[row][col]

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

    return false
}

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = m * n - 1;

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

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

        return false;
    }
};

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1

        while left <= right:
            mid = left + (right - left) // 2
            row, col = divmod(mid, n)
            value = matrix[row][col]

            if value == target:
                return True
            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

var searchMatrix = function(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;

  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const row = Math.floor(mid / n);
    const col = mid % n;
    const value = matrix[row][col];

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

  return false;
};