Search an Element in a Sorted 2D Matrix Optimal Approach using Binary Search

Problem Statement❯

You are given a 2D matrix of integers with the following properties:

Each row is sorted in ascending order.
The first integer of each row is greater than the last integer of the previous row.

Your task is to determine whether a given target number exists in the matrix.

If the number exists, return true; otherwise, return false.

Examples❯

Matrix	Target	Output	Description
[[1, 4, 7, 10, 13],[14, 17, 20, 23, 26],[27, 30, 33, 36, 39],[40, 43, 46, 49, 52],[53, 56, 59, 62, 65]]	36	true	36 exists in the third row and fourth column
[[1, 3, 5],[7, 9, 11],[13, 15, 17]]	9	true	9 exists in the second row
[[1, 3, 5],[7, 9, 11],[13, 15, 17]]	6	false	6 is not present in any row
[[2, 4, 6]]	4	true	Single row matrix, 4 is present
[[2, 4, 6]]	5	false	Single row matrix, 5 is not present
[[2], [5], [8], [11]]	11	true	Single column matrix, 11 is the last element
[[2], [5], [8], [11]]	3	false	Single column matrix, 3 is not present
[]	1	false	Empty matrix, nothing to search
[[]]	0	false	Matrix with empty row, no data to search

Visualization Player

Solution❯

To determine whether a given number exists in a sorted 2D matrix, we use a binary search approach, but with a twist: we treat the 2D matrix as a 1D sorted array.

Understanding the Matrix Structure

The matrix has two important properties:

Each row is sorted in increasing order.
The first number of a row is greater than the last number of the previous row. This means the entire matrix is sorted when viewed as one long list.

How We Search

We imagine flattening the matrix into a 1D array (without actually doing it in code). If the matrix has m rows and n columns, then:

The virtual 1D index mid can be mapped to 2D as matrix[row][col], where:

row = Math.floor(mid / n)
col = mid % n

Different Possibilities to Consider

If the matrix is empty (e.g., []), we simply return false. There is no data to search.
If the matrix has rows but no columns (e.g., [[]]), we also return false.
If the target is smaller than the first element, it cannot exist in the matrix.
If the target is greater than the last element, it also cannot exist.
For all other values, we run binary search from start = 0 to end = m * n - 1.

At each step, we check if the mid element matches the target:

If yes → return true
If target is smaller → search left half
If target is greater → search right half

This approach ensures we don’t have to scan every row or column manually. It works in O(log(m × n)) time, which is highly efficient for large matrices.

By converting between 1D and 2D indices using basic math, we can search across rows and columns in a clean and fast way.

Algorithm Steps❯

Let the matrix have m rows and n columns.
Initialize start = 0 and end = m * n - 1.
While start ≤ end:
→ Compute mid = (start + end) / 2.
→ Convert mid to 2D coordinates: row = mid / n, col = mid % n.
→ If matrix[row][col] == target, return true.
→ If matrix[row][col] < target, move start = mid + 1.
→ If matrix[row][col] > target, move end = mid - 1.
Return false if target not found.

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class MatrixSearch {
  public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int start = 0;
    int end = rows * cols - 1;

    while (start <= end) {
      int mid = start + (end - start) / 2;
      int row = mid / cols;           // Map 1D mid to 2D row
      int col = mid % cols;           // Map 1D mid to 2D col

      if (matrix[row][col] == target) return true;
      else if (matrix[row][col] < target) start = mid + 1;
      else end = mid - 1;
    }
    return false;
  }

  public static void main(String[] args) {
    int[][] matrix = {
      {1, 3, 5, 7},
      {10, 11, 16, 20},
      {23, 30, 34, 60}
    };
    int target = 3;
    System.out.println("Found: " + searchMatrix(matrix, target));
  }
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	The target is found at the very first middle index.
Average Case	O(log (m * n))	The binary search is applied over a virtual 1D array of m * n elements.
Worst Case	O(log (m * n))	The binary search checks until one element is left, typical of a logarithmic search space.

Space Complexity❯

O(1)

Explanation: The algorithm uses constant space, no extra data structures are used apart from a few variables.

⬅ Previous TopicRow with Maximum Number of 1's

Next Topic ⮕Search in Row and Column-wise Sorted Matrix

Comments

Loading comments...