Search in a Sorted 2D Matrix Using Binary Search

Given an M x N integer matrix matrix and an integer target, return true if target exists in the matrix, otherwise return false.

The matrix has two special properties:

• Each row is sorted from left to right.

• The first element of every row is greater than the last element of the previous row.

Brute Force Approach

The simplest thought is to just check every value one by one.

If any cell matches the target, the search can stop immediately.

This approach is useful as a starting point because it matches exactly what the problem is asking, even though it does not use the matrix properties in a smart way.

Algorithm

• First, check whether the matrix is empty. This is needed so the code does not try to access a row that does not exist.

• Traverse each row one by one because the target can be anywhere in the matrix.

• Inside every row, traverse each column and compare the current cell with the target.

• If the current value matches the target, return true immediately because the answer has already been found.

• If the full matrix is checked and no match appears, return false because the target is not present.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(M x N), M is the number of rows, N is number of columns, because in the worst case every cell of the matrix may need to be checked.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The unlocking observation is this: the matrix is not just row-wise sorted. It is sorted in a stronger way. The last value of one row is smaller than the first value of the next row. Because of that, if the matrix is read row by row, it becomes one fully sorted sequence.

For example:

[[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]

behaves like:

[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

Now the problem starts looking exactly like normal binary search. The only tricky part is that the matrix is still stored in 2D form. So instead of actually creating a new 1D array, a virtual 1D index is used.

If there are cols columns:

• row = mid / cols tells which row the middle position belongs to.

• col = mid % cols tells which column inside that row should be checked.

This is why binary search works here without flattening the matrix in memory.

Algorithm

• First, check whether the matrix is empty. This is needed so the number of columns can be read safely and Store rows and cols because these values are used again and again to control the search and map indices correctly.

• Treat the full matrix like a virtual sorted array of size rows * cols. This is done because binary search needs one sorted search space and Keep two pointers, low = 0 and high = rows * cols - 1, so the search starts with the entire virtual array.

• Find the middle index using mid = low + (high - low) / 2. This gives the current candidate position without risking overflow in languages like C++ and Java.

• Convert that 1D index into a real matrix position using row = mid / cols and col = mid % cols. This step is needed because the data is stored as a matrix, not as an actual 1D array.

• Compare matrix[row][col] with the target. If both are equal, return true because the target has been found.

• If the middle value is smaller than the target, move low to mid + 1 because every value on the left side is also too small.

• Otherwise, move high to mid - 1 because the middle value and everything on the right side are too large.

• If the loop finishes, return false because no position matched the target.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(log₂(M x N)), M is the number of rows and N is the number of columns, because our search space is M x N so binary search gives us log₂(M xN)

Space Complexity: O(1), because constant space is used.