Why Search in 2D Matrix in DSA Java?

The Big Idea

What if you could find any number in a giant grid without checking every single spot?

The Scenario

Imagine you have a big spreadsheet with rows and columns full of numbers. You want to find if a certain number is there. You start checking each cell one by one, moving left to right, top to bottom.

The Problem

This manual way is very slow and tiring. If the spreadsheet is huge, it takes a long time to check every cell. You might also lose track or make mistakes while searching.

The Solution

Using a smart search method for a 2D matrix helps you find the number quickly without checking every cell. It uses the order in rows and columns to skip many cells, saving time and effort.

Before vs After

✗ Before

for (int i = 0; i < matrix.length; i++) {
  for (int j = 0; j < matrix[0].length; j++) {
    if (matrix[i][j] == target) return true;
  }
}
return false;

✓ After

int row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
  if (matrix[row][col] == target) return true;
  else if (matrix[row][col] > target) col--;
  else row++;
}
return false;

What It Enables

This method lets you find any number in a sorted 2D matrix quickly and confidently, even if the matrix is very large.

Real Life Example

Think of a library catalog arranged by shelves (rows) and books (columns) sorted by title. You can quickly find a book by skipping shelves or books that are too early or too late alphabetically.

Key Takeaways

Manual search checks every cell, which is slow for big matrices.

Smart search uses matrix order to skip unnecessary checks.

It saves time and reduces errors when searching.

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