Search Target in a 2D Sorted Matrix
Binary Search Approach

⬅ Previous Topic

Search in Row and Column-wise Sorted Matrix

Next Topic ⮕

Matrix Median

Topic Contents

Problem Examples Solution Algorithm Code Time Space

Problem Statement

You are given a 2D matrix of size N × M where:

Each row is sorted in non-decreasing order from left to right.
The first element of each row is greater than the last element of the previous row.

Your task is to determine whether a given target value exists in the matrix or not.

If the target is found, return true; otherwise, return false.

Examples❯

Matrix	Target	Result	Description
[[1, 3, 5], [7, 9, 11], [13, 15, 17]]	9	true	9 is present in the second row
[[1, 3, 5], [7, 9, 11], [13, 15, 17]]	6	false	6 is not present anywhere in the matrix
[[5, 10, 15], [20, 25, 30]]	5	true	5 is the first element
[[5, 10, 15], [20, 25, 30]]	30	true	30 is the last element
[[5, 10, 15], [20, 25, 30]]	35	false	Target is greater than all elements
[[5, 10, 15], [20, 25, 30]]	1	false	Target is smaller than all elements
[[10]]	10	true	Single element matrix, target matches
[[10]]	5	false	Single element matrix, target does not match
[]	10	false	Empty matrix, nothing to search

Solution❯

To search for a number in a special type of 2D matrix where each row is sorted and the first element of every row is greater than the last of the previous row, we can treat the matrix like a flattened sorted 1D array.

Imagine laying out all the rows into a single list and then applying binary search on that list. Since the matrix behaves like a sorted list, we can efficiently find whether the target exists using this approach.

Handling Different Cases

1. Normal Case: For a matrix like [[1, 3, 5], [7, 9, 11], [13, 15, 17]] and target = 9, we start our search from the middle element. If it’s not a match, we reduce our search space to the left or right half depending on comparison, just like binary search in arrays.

2. Edge Case (target is smallest or largest): If the target is the smallest number, it will be at the top-left corner. If it’s the largest, it will be at the bottom-right corner. Both are valid positions and must be included in the search.

3. Single Element Matrix: If the matrix has only one element, we directly compare it with the target. It’s the simplest base case.

4. Empty Matrix: If the matrix is empty (i.e., has no rows), there’s nothing to search, and we return false immediately.

Why Binary Search Works

Since the matrix is globally sorted (across rows and columns), binary search lets us eliminate half of the matrix in every step. By converting the single index into 2D coordinates row = mid / M and col = mid % M, we can access the matrix element in constant time.

This approach works in O(log(N × M)) time and is highly efficient even for large matrices.

Algorithm Steps

Let start = 0, end = N * M - 1.
While start ≤ end:
→ Compute mid = (start + end) / 2.
→ Convert mid to row = mid / M and col = mid % M.
→ Compare mat[row][col] with target.
If equal, return true.
If target < mat[row][col], move left (end = mid - 1).
If target > mat[row][col], move right (start = mid + 1).
If loop ends, return false (not found).

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class MatrixSearch {
  public static boolean searchMatrix(int[][] mat, int target) {
    int rows = mat.length;
    int cols = mat[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 index to 2D row
      int col = mid % cols;    // Map 1D index to 2D col

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

  public static void main(String[] args) {
    int[][] mat = {
      {1, 4, 7},
      {8, 11, 15},
      {17, 20, 23}
    };
    int target = 11;
    System.out.println("Found? " + searchMatrix(mat, target));
  }
}

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	When the target is found in the first mid calculation.
Average Case	O(log(N * M))	The binary search reduces the search space by half in each iteration over the virtual flattened array.
Worst Case	O(log(N * M))	All elements are searched using binary search till the last comparison.

Space Complexity

O(1)

Explanation: No extra space is used; the algorithm uses a constant number of variables.

⬅ Previous Topic

Search in Row and Column-wise Sorted Matrix

Next Topic ⮕

Matrix Median

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Search Target in a 2D Sorted Matrix
Binary Search Approach

Problem Statement

Examples❯

Solution❯

Handling Different Cases

Why Binary Search Works

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Search Target in a 2D Sorted MatrixBinary Search Approach

Problem Statement

Examples❯

Solution❯

Handling Different Cases

Why Binary Search Works

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Search Target in a 2D Sorted Matrix
Binary Search Approach