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)
1public class Solution {
2 public bool SearchMatrix(int[][] matrix, int target) {
3 int m = matrix.Length;
4 int n = matrix[0].Length;
5 int left = 0, right = m * n - 1;
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 int midVal = matrix[mid / n][mid % n];
9 if (midVal == target) return true;
10 else if (midVal < target) left = mid + 1;
11 else right = mid - 1;
12 }
13 return false;
14 }
15}This C# code demonstrates mapping of linear index to matrix coordinates, ensuring binary search can be executed on the conceptual 1D array version of the matrix.
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)
1In this Java implementation, the two-step binary search efficiently identifies the row first and then applies binary search on the row elements, maintaining time efficiency.