Sponsored
Sponsored
The matrix can be viewed as a single sorted list. Hence, we can perform a binary search on the entire matrix by treating it as a 1D array. Suppose we have a matrix of size m x n, any element in the matrix can be accessed using a single index calculated as follows:
Element at index k can be accessed using matrix[k / n][k % n], where / and % represent integer division and modulus operations, respectively.
This approach ensures that the solution operates in O(log(m * n)) time complexity as required.
Time complexity: O(log(m * n))
Space complexity: O(1)
1function searchMatrix(matrix, target) {
2 const m = matrix.length;
3 const n = matrix[0].length;
4 let left = 0, right = m * n - 1;
5 while (left <= right) {
6 const mid = Math.floor(left + (right - left) / 2);
7 const midVal = matrix[Math.floor(mid / n)][mid % n];
8 if (midVal === target) return true;
9 else if (midVal < target) left = mid + 1;
10 else right = mid - 1;
11 }
12 return false;
13}The JavaScript solution utilizes Math operations to simulate 1D indices on the matrix to facilitate a binary search operation effectively, ensuring optimality in time complexity.
The problem also allows for a two-step binary search owing to the special properties of the matrix. First, we identify the row which potentially contains the target by performing binary search on first elements of each row. Then, we conduct a binary search in that specific row.
Although not strictly O(log(m * n)), this approach exploits the matrix's properties in an efficient manner for similar effective results.
Time complexity: O(log(m) + log(n))
Space complexity: O(1)
This JavaScript function implements a two-phase binary search with row choice as the preliminary step, ensuring efficient target location checks in the matrix.