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)
1#include <vector>
2using namespace std;
3class Solution {
4public:
5 bool searchMatrix(vector<vector<int>>& matrix, int target) {
6 int m = matrix.size();
7 int n = matrix[0].size();
8 int left = 0, right = m * n - 1;
9 while (left <= right) {
10 int mid = left + (right - left) / 2;
11 int midVal = matrix[mid / n][mid % n];
12 if (midVal == target) return true;
13 else if (midVal < target) left = mid + 1;
14 else right = mid - 1;
15 }
16 return false;
17 }
18};This C++ solution employs a similar approach by calculating the middle index and accessing matrix elements using the calculated row and column indices from the middle index.
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.