Search in 2D Matrix in DSA C++ - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Repeat until found or out of bounds

Start searching from the top-right corner. Move left if target is smaller, move down if target is larger, repeat until found or no more elements.

Execution Sample

DSA C++

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

Search target in sorted 2D matrix by starting at top-right and moving left or down.

Execution Table

Step	Operation	Current Position (row,col)	Current Element	Comparison with Target	Pointer Changes	Visual State
1	Start	(0,4)	15	15 > 5	Move left: col = 3	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
2	Compare	(0,3)	7	7 > 5	Move left: col = 2	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
3	Compare	(0,2)	5	5 == 5	Found target	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
4	Exit	-	-	-	-	Target found at (0,2)

💡 Target found at position (0,2), search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
row	0	0	0	0	0
col	4	3	2	2	2
current_element	15	7	5	5	5

Key Moments - 3 Insights

Why do we start searching from the top-right corner?

Because from the top-right, moving left decreases values and moving down increases values, allowing efficient elimination of rows or columns as shown in steps 1 and 2 of the execution_table.

What happens if the current element is greater than the target?

We move left by decreasing the column index (col--) to find smaller elements, as seen in steps 1 and 2 where col changes from 4 to 3 and then 2.

Why do we stop when col < 0 or row >= number of rows?

Because it means we have searched all possible positions without finding the target, so the search ends. This is the exit condition in the while loop.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'col' after step 2?

A 2

B 3

C 4

D 1

💡 Hint

Check the 'Pointer Changes' and 'Current Position' columns in step 2 of execution_table.

At which step does the algorithm find the target?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Comparison with Target' and 'Operation' columns to see when target == current element.

If the target was 21, what would be the next move after starting at (0,4)?

A Move left to (0,3)

B Move down to (1,4)

C Stop search

D Move right to (0,5)

💡 Hint

Compare target 21 with element 15 at (0,4) and check the movement rules in concept_flow.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element
- If current > target, move left
- If current < target, move down
- Repeat until found or out of bounds
- Efficient for sorted rows and columns

Full Transcript

This visualization shows how to search a target value in a 2D matrix where each row and column is sorted. We start at the top-right corner. If the current element is greater than the target, we move left to smaller elements. If it is smaller, we move down to larger elements. We repeat this until we find the target or run out of matrix bounds. The execution table traces each step, showing the current position, element, comparison, and pointer changes. The variable tracker shows how row and column indices change. Key moments clarify why we start at the top-right and how movement decisions are made. The quiz tests understanding of pointer changes and search steps.