To search for a number in a special type of 2D matrix where each row is sorted and the first element of every row is greater than the last of the previous row, we can treat the matrix like a flattened sorted 1D array.
Imagine laying out all the rows into a single list and then applying binary search on that list. Since the matrix behaves like a sorted list, we can efficiently find whether the target exists using this approach.
Handling Different Cases
1. Normal Case: For a matrix like [[1, 3, 5], [7, 9, 11], [13, 15, 17]]
and target = 9, we start our search from the middle element. If it’s not a match, we reduce our search space to the left or right half depending on comparison, just like binary search in arrays.
2. Edge Case (target is smallest or largest): If the target is the smallest number, it will be at the top-left corner. If it’s the largest, it will be at the bottom-right corner. Both are valid positions and must be included in the search.
3. Single Element Matrix: If the matrix has only one element, we directly compare it with the target. It’s the simplest base case.
4. Empty Matrix: If the matrix is empty (i.e., has no rows), there’s nothing to search, and we return false
immediately.
Why Binary Search Works
Since the matrix is globally sorted (across rows and columns), binary search lets us eliminate half of the matrix in every step. By converting the single index into 2D coordinates row = mid / M
and col = mid % M
, we can access the matrix element in constant time.
This approach works in O(log(N × M)) time and is highly efficient even for large matrices.