Sponsored
Sponsored
This approach begins searching from the top-right corner of the matrix. If the current element is equal to the target, return true. If the current element is greater than the target, move left. If the current element is less than the target, move down. This method effectively narrows down the search space, taking advantage of the sorted property of the matrix.
Time Complexity: O(m + n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no extra space is used.
1#include <vector>
2
3class Solution {
4public:
5 bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
6 int row = 0, col = matrix[0].size() - 1;
7 while (row < matrix.size() && col >= 0) {
8 if (matrix[row][col] == target) {
9 return true;
10 } else if (matrix[row][col] > target) {
11 col--;
12 } else {
13 row++;
14 }
15 }
16 return false;
17 }
18};The C++ solution works similarly to the C solution. It initializes searching from the top-right corner and iteratively adjusts its position based on the comparison between the current element and the target. This efficiently reduces the search space.
This approach uses binary search on each row of the matrix. Since each row is sorted, binary search can efficiently determine if the target exists within the row. If found in any row, the function returns true.
Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).
1public
The Java implementation utilizes a helper method `binarySearch` to perform searches within each matrix row. By executing a binary search for each row, it efficiently checks for the existence of the target value.