74. Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n
matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
The Solution to the above solution
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int start=0;
int n=matrix[0].size();
int fir=matrix[start][0];
int last=matrix[start][n-1];
while(target>fir && target>last){
start++;
if(start>=matrix.size()){
return false;
}
fir=matrix[start][0];
last=matrix[start][n-1];
}
cout<<start<<endl;
int low=0;
int high=n-1,mid;
while(low<=high){
mid=(low+high)/2;
cout<<mid<<" ";
if(matrix[start][mid]==target){
return true;
}
else if(matrix[start][mid]<target){
low=mid+1;
}
else {
high=mid-1;
}
}
if(matrix[start][mid]==target){
return true;
}
return false;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.