Search in 2D Matrix in DSA Java

Mental Model

We treat the 2D matrix like a sorted list and use a smart search to find the target quickly.

Analogy: Imagine a phone book sorted by last name and first name. You look for a name by jumping to the middle, then deciding to go up or down, cutting the search area in half each time.

Matrix:
[1, 3, 5, 7]
[10, 11, 16, 20]
[23, 30, 34, 50]

We imagine this as a single sorted list:
1 -> 3 -> 5 -> 7 -> 10 -> 11 -> 16 -> 20 -> 23 -> 30 -> 34 -> 50 -> null

Dry Run Walkthrough

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

Goal: Find if the target number 3 exists in the matrix.

Step 1: Calculate mid index of the virtual list: mid = (0 + 11) / 2 = 5

Virtual list indices: 0..11, mid=5 corresponds to matrix[1][1] = 11

Why: We start by checking the middle element to reduce search space.

Step 2: Compare target 3 with mid element 11; since 3 < 11, search left half: end = mid - 1 = 4

Search range now indices 0..4, elements: 1,3,5,7,10

Why: Target is smaller, so we discard right half.

Step 3: Calculate new mid: mid = (0 + 4) / 2 = 2, corresponds to matrix[0][2] = 5

Mid element is 5

Why: Check middle of the reduced range.

Step 4: Compare target 3 with 5; since 3 < 5, search left half: end = mid - 1 = 1

Search range indices 0..1, elements: 1,3

Why: Target is smaller, discard right half again.

Step 5: Calculate new mid: mid = (0 + 1) / 2 = 0, corresponds to matrix[0][0] = 1

Mid element is 1

Why: Check middle of the new range.

Step 6: Compare target 3 with 1; since 3 > 1, search right half: start = mid + 1 = 1

Search range indices 1..1, element: 3

Why: Target is bigger, discard left half.

Step 7: Calculate new mid: mid = (1 + 1) / 2 = 1, corresponds to matrix[0][1] = 3

Mid element is 3

Why: Check middle of the last range.

Step 8: Compare target 3 with 3; found target!

Target found at matrix[0][1]

Why: We found the target, so we stop.

Result:

Target 3 found at matrix[0][1]

Annotated Code

DSA Java

public class Search2DMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false; // handle empty matrix
        }
        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 midValue = matrix[mid / cols][mid % cols];

            if (midValue == target) {
                return true; // found target
            } else if (midValue < target) {
                start = mid + 1; // search right half
            } else {
                end = mid - 1; // search left half
            }
        }
        return false; // target not found
    }

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

int mid = start + (end - start) / 2;

Calculate middle index of current search range to avoid overflow

int midValue = matrix[mid / cols][mid % cols];

Map 1D mid index to 2D matrix row and column

if (midValue == target) { return true; }

Check if mid element is the target

else if (midValue < target) { start = mid + 1; }

If mid element less than target, search right half

else { end = mid - 1; }

If mid element greater than target, search left half

Output

Target 3 found

Complexity Analysis

Time: O(log(m*n)) because we perform binary search on all elements treated as a single sorted list

Space: O(1) because we use only a few variables and no extra space proportional to input size

vs Alternative: A naive approach would scan every element O(m*n), which is slower than binary search's O(log(m*n))

Edge Cases

Empty matrix

Returns false immediately because there are no elements to search

DSA Java

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

Target smaller than all elements

Binary search narrows down and returns false after checking all possibilities

DSA Java

while (start <= end)

Target larger than all elements

Binary search narrows down and returns false after checking all possibilities

DSA Java

while (start <= end)

When to Use This Pattern

When you see a 2D matrix sorted row-wise and column-wise and need to find a value quickly, use binary search treating it as a 1D sorted list.

Common Mistakes

Mistake: Using mid / rows instead of mid / cols to find row index
Fix: Use mid / cols for row and mid % cols for column to correctly map 1D index to 2D

Mistake: Not checking if matrix is empty before accessing matrix[0]
Fix: Add a check for empty matrix or empty rows before starting search

Summary

Searches a target value in a sorted 2D matrix using binary search.

Use when the matrix rows and columns are sorted and you want fast search.

Treat the 2D matrix as a single sorted list and map indices carefully.

Practice

1. What is the main idea behind searching a target value in a 2D matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row?

easy

A. Treat the 2D matrix as a sorted 1D array and apply binary search

B. Search each row linearly until the target is found

C. Use a hash map to store all elements for quick lookup

D. Start from the bottom-left corner and move diagonally

Solution

1. Step 1: Understand matrix sorting property

   Each row is sorted and the first element of a row is greater than the last element of the previous row, so the entire matrix can be seen as a sorted list.

2. Step 2: Apply binary search on the matrix

   By treating the matrix as a 1D sorted array, binary search can be used efficiently to find the target.

3. Final Answer:

   Treat the 2D matrix as a sorted 1D array and apply binary search -> Option A

4. Quick Check:

   Matrix sorted row-wise = binary search [OK]

Hint: Think of the matrix as one sorted list for fast search [OK]

Common Mistakes:

• Searching each row linearly wastes time
• Using hash map wastes extra space
• Starting from bottom-left only works for different matrix types

2. Which of the following Java code snippets correctly calculates the middle index for binary search on a 2D matrix treated as a 1D array with total elements rows * cols?

easy

A. int mid = (low * high) / 2;

B. int mid = (low + high) / 2;

C. int mid = (low - high) / 2;

D. int mid = low + (high - low) / 2;

Solution

1. Step 1: Understand safe mid calculation

   Using low + (high - low) / 2 prevents integer overflow compared to (low + high) / 2.

2. Step 2: Check other options

   int mid = (low - high) / 2; and D do not correctly calculate mid index for binary search.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option D

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

Hint: Use low + (high - low) / 2 to avoid overflow [OK]

Common Mistakes:

• Using (low + high) / 2 can cause overflow
• Using subtraction incorrectly for mid
• Multiplying low and high is wrong

3. Given the following Java code to search for target 5 in the matrix int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};, what will be the output?

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0, high = rows * cols - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int midValue = matrix[mid / cols][mid % cols];
        if (midValue == target) return true;
        else if (midValue < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

System.out.println(searchMatrix(matrix, 5));

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand matrix and target

   The matrix contains 5 at position (0,2). The binary search checks mid values correctly by converting 1D mid to 2D indices.

2. Step 2: Trace binary search steps

   Binary search finds 5 and returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   5 found in matrix = true [OK]

Hint: Convert mid to row and col using mid/cols and mid%cols [OK]

Common Mistakes:

• Using wrong index conversion for mid
• Confusing row and column indices
• Returning false before full search

4. Identify the bug in the following Java method that searches a target in a 2D matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row:

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0, high = rows * cols;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int midValue = matrix[mid / cols][mid % cols];
        if (midValue == target) return true;
        else if (midValue < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

medium

A. The mid calculation causes overflow

B. The high index should be rows * cols - 1, not rows * cols

C. The matrix indexing is incorrect

D. The loop condition should be low < high

Solution

1. Step 1: Check high initialization

   High should be the last valid index, which is rows * cols - 1, not rows * cols (which is out of bounds).

2. Step 2: Verify other parts

   Mid calculation and indexing are correct; loop condition low <= high is standard for binary search.

3. Final Answer:

   The high index should be rows * cols - 1, not rows * cols -> Option B

4. Quick Check:

   High index off by one causes error [OK]

Hint: High index = total elements - 1 for zero-based arrays [OK]

Common Mistakes:

• Setting high to rows * cols causes out-of-bounds
• Changing loop condition incorrectly
• Miscomputing mid index

5. You have a 2D matrix where each row is sorted in ascending order, but the first integer of each row is NOT necessarily greater than the last integer of the previous row. Which approach is best to search for a target value efficiently?

hard

A. Use binary search treating matrix as 1D sorted array

B. Perform binary search on each row separately

C. Start from top-right corner and move left/down based on comparison

D. Use linear search over all elements

Solution

1. Step 1: Understand matrix property

   Rows are sorted but no guarantee that next row's first element is greater than previous row's last element, so treating as 1D sorted array is invalid.

2. Step 2: Choose search method

   Starting from top-right corner, move left if current > target, move down if current < target, efficiently narrows search.

3. Final Answer:

   Start from top-right corner and move left/down based on comparison -> Option C

4. Quick Check:

   Top-right corner search = efficient for partially sorted matrix [OK]

Hint: Top-right corner search works when rows sorted but no global order [OK]

Common Mistakes:

• Applying 1D binary search wrongly
• Searching each row fully wastes time
• Using linear search is slow