Search in 2D Matrix
Search for a target value in a sorted 2D matrix efficiently. Two common variants: (1) Matrix sorted row-wise and column-wise - use staircase search in O(m+n). (2) Matrix treated as flattened sorted array - use binary search in O(log(m×n)). This problem demonstrates how to leverage sorted properties in multiple dimensions and convert between 1D and 2D indexing.
Visualization
Interactive visualization for Search in 2D Matrix
Sample Matrix (sorted):
[1, 4, 7, 11] [2, 5, 8, 12] [3, 6, 9, 16] [10, 13, 14, 17]
Interactive visualization with step-by-step execution
Implementation
1// Approach 1: Binary search (fully sorted)
2function searchMatrix(matrix: number[][], target: number): boolean {
3 if (!matrix.length || !matrix[0].length) return false;
4
5 const m = matrix.length, n = matrix[0].length;
6 let left = 0, right = m * n - 1;
7
8 while (left <= right) {
9 const mid = Math.floor((left + right) / 2);
10 const midValue = matrix[Math.floor(mid / n)][mid % n];
11
12 if (midValue === target) return true;
13 if (midValue < target) left = mid + 1;
14 else right = mid - 1;
15 }
16
17 return false;
18}
19
20// Approach 2: Staircase search (row & col sorted)
21function searchMatrixStaircase(matrix: number[][], target: number): boolean {
22 if (!matrix.length || !matrix[0].length) return false;
23
24 let row = 0;
25 let col = matrix[0].length - 1;
26
27 while (row < matrix.length && col >= 0) {
28 if (matrix[row][col] === target) return true;
29 if (matrix[row][col] > target) col--;
30 else row++;
31 }
32
33 return false;
34}Deep Dive
Theoretical Foundation
Two elegant approaches depending on matrix properties: **Approach 1 (Fully Sorted):** Treat m×n matrix as flattened 1D array with m*n elements. Apply binary search with index conversion: for index i, row=i/n, col=i%n. Time: O(log(m×n)). **Approach 2 (Row & Column Sorted):** Use staircase search starting from top-right (or bottom-left). At each step, eliminate either an entire row or column based on comparison. If target < current, move left (eliminate column). If target > current, move down (eliminate row). Time: O(m+n). Both approaches avoid O(m×n) brute force.
Complexity
Time
O(1)
O(log(m×n)) or O(m+n)
O(log(m×n)) or O(m+n)
Space
O(1)
Applications
Industry Use
Database query optimization (indexed tables)
Image processing (searching in gradient matrices)
Game boards (Tic-tac-toe, Chess position search)
Spreadsheet range queries
Spatial data structures
2D range search in GIS systems
Use Cases
Related Algorithms
Binary Search
Binary Search is one of the most efficient searching algorithms with O(log n) time complexity. It works on sorted arrays by repeatedly dividing the search space in half, eliminating half of the remaining elements with each comparison. This divide-and-conquer approach makes it exponentially faster than linear search for large datasets.
Linear Search
Linear Search, also known as Sequential Search, is the simplest searching algorithm that checks each element in a list sequentially until the target element is found or the end is reached. Despite its O(n) time complexity, it's the only option for unsorted data and remains practical for small datasets or when simplicity is crucial.
Jump Search
Jump Search is an efficient algorithm for sorted arrays that combines the benefits of linear and binary search. Instead of checking every element (linear) or dividing the array (binary), it jumps ahead by fixed steps of √n and then performs linear search within the identified block. This approach achieves O(√n) time complexity, making it faster than linear search while being simpler than binary search for certain applications.
Interpolation Search
Interpolation Search is an improved variant of binary search specifically optimized for uniformly distributed sorted arrays. Instead of always checking the middle element, it estimates the target's position based on the target value relative to the range of values, similar to how humans search a phone book. Achieves O(log log n) average time for uniformly distributed data, significantly faster than binary search's O(log n).