Search in a Sorted 2D Matrix

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.

Understanding the Problem

We are given a 2D matrix and a target number. The matrix has two special properties:

• Each row is sorted in increasing order from left to right.
• The first number of each row is greater than the last number of the previous row.

This means if we "flatten" the matrix, the elements form a fully sorted 1D array. Our task is to determine whether the target number exists in the matrix. A beginner might think of scanning every row and column, but that would be inefficient. Instead, we will use a binary search approach that treats the entire 2D matrix as a sorted 1D list — without actually flattening it.

Step-by-Step Solution with Example

step 1: Represent the matrix and target

matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
target = 3

We want to check whether the number 3 exists in this matrix.

step 2: Understand the matrix as a virtual 1D array

The matrix has m = 3 rows and n = 4 columns. So the total number of elements is m × n = 12.

Imagine indexing this matrix from 0 to 11, like a normal 1D array. The key idea is:

• row = Math.floor(index / n)
• col = index % n

This lets us map any 1D index to a 2D coordinate in the matrix.

step 3: Initialize binary search

We set start = 0 and end = m × n - 1 = 11.

We will now perform binary search between these indices.

step 4: Perform the binary search loop

Repeat the following until start > end:

1. Find the middle index: mid = Math.floor((start + end) / 2)
2. Map this index to 2D: row = Math.floor(mid / n), col = mid % n
3. Check matrix[row][col] against the target:
• If it matches → return true
• If it’s less than the target → move to right half: start = mid + 1
• If it’s more than the target → move to left half: end = mid - 1

For our example, 3 is found at index 1 (which maps to row 0, column 1).

step 5: Return the result

If the binary search completes without finding the target, return false.

Edge Cases

• Empty matrix: If the matrix is [], return false. No data to search.
• Matrix with empty rows: For example, [[]] → no columns → return false.
• Target smaller than the smallest element: return false.
• Target greater than the largest element: return false.
• These checks help us avoid unnecessary work and prevent runtime errors.

Finally

This approach is efficient and elegant. By treating the 2D matrix as a virtual 1D sorted array, we leverage binary search for O(log(m × n)) time complexity. This is especially helpful for large matrices.

For beginners, it's important to understand how index mapping works and how binary search helps us reduce the search space efficiently. Always check for edge cases first, then implement the main logic clearly and step by step.

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

#include <stdio.h>
#include <stdbool.h>

bool searchMatrix(int matrix[][4], int rows, int cols, int target) {
    int start = 0, end = rows * cols - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        int row = mid / cols;
        int col = mid % cols;

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

int main() {
    int matrix[3][4] = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    int target = 3;
    printf("Found: %s\n", searchMatrix(matrix, 3, 4, target) ? "true" : "false");
    return 0;
}

#include <iostream>
using namespace std;

bool searchMatrix(int matrix[][4], int rows, int cols, int target) {
    int start = 0, end = rows * cols - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        int row = mid / cols;
        int col = mid % cols;

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

int main() {
    int matrix[3][4] = {
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    int target = 3;
    cout << "Found: " << (searchMatrix(matrix, 3, 4, target) ? "true" : "false") << endl;
    return 0;
}

def search_matrix(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])
    start, end = 0, rows * cols - 1

    while start <= end:
        mid = (start + end) // 2
        row = mid // cols
        col = mid % cols

        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            start = mid + 1
        else:
            end = mid - 1
    return False

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]
target = 3
print("Found:", search_matrix(matrix, target))

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

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

            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));
    }
}

function searchMatrix(matrix, target) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    let start = 0, end = rows * cols - 1;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        let row = Math.floor(mid / cols);
        let col = mid % cols;

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

const matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
];
const target = 3;
console.log("Found:", searchMatrix(matrix, target));

package main

import (
    "fmt"
)

func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    cols := len(matrix[0])
    start, end := 0, rows*cols-1

    for start <= end {
        mid := (start + end) / 2
        row := mid / cols
        col := mid % cols

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

func main() {
    matrix := [][]int{
        {1, 3, 5, 7},
        {10, 11, 16, 20},
        {23, 30, 34, 60},
    }
    target := 3
    fmt.Println("Found:", searchMatrix(matrix, target))
}

fn search_matrix(matrix: &Vec<Vec<i32>>, target: i32) -> bool {
    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut start = 0;
    let mut end = rows * cols - 1;

    while start <= end {
        let mid = (start + end) / 2;
        let row = mid / cols;
        let col = mid % cols;

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

fn main() {
    let matrix = vec![
        vec![1, 3, 5, 7],
        vec![10, 11, 16, 20],
        vec![23, 30, 34, 60],
    ];
    let target = 3;
    println!("Found: {}", search_matrix(&matrix, target));
}

fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
    val rows = matrix.size
    val cols = matrix[0].size
    var start = 0
    var end = rows * cols - 1

    while (start <= end) {
        val mid = (start + end) / 2
        val row = mid / cols
        val col = mid % cols

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

fun main() {
    val matrix = arrayOf(
        intArrayOf(1, 3, 5, 7),
        intArrayOf(10, 11, 16, 20),
        intArrayOf(23, 30, 34, 60)
    )
    val target = 3
    println("Found: ${searchMatrix(matrix, target)}")
}

func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
    let rows = matrix.count
    let cols = matrix[0].count
    var start = 0
    var end = rows * cols - 1

    while start <= end {
        let mid = (start + end) / 2
        let row = mid / cols
        let col = mid % cols

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

let matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]
let target = 3
print("Found: \(searchMatrix(matrix, target))")

function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let start = 0, end = rows * cols - 1;

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    const row = Math.floor(mid / cols);
    const col = mid % cols;

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

const matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
];
const target = 3;
console.log("Found:", searchMatrix(matrix, target));

Time complexity

Space complexity

O(1)

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