Algorithm:
- Apply Binary Search to find the row (where the potential target might be present)
- After find the row, apply Binary Search on that row. If the target element is present, we return true otherwise we return false.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int getRow = findRow(matrix, target);
if(getRow==-1)
return false;
int low = 0;
int high = matrix[0].length-1;
while(low<=high){
int mid = low + (high-low)/2;
if(matrix[getRow][mid]==target)
return true;
else if(matrix[getRow][mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return false;
}
int findRow(int matrix[][], int target){
int low = 0;
int high = matrix.length-1;
int lastCol = matrix[0].length-1;
while(low<=high){
int mid = low + (high-low)/2;
if(matrix[mid][0]<=target && matrix[mid][lastCol]>=target)
return mid;
else if(matrix[mid][0]<target)
low = mid + 1;
else
high = mid-1;
}
return -1;
}
}
Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀
If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7
Top comments (0)