Problem Link
Write an efficient algorithm that searches for a value target
in an m x n
integer matrix 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.
In this problem we can find the appropriate row number by using binary search
Then similarly we can find the appropriate row number by using binary search.
So, this solution requires two binary search.
Code:
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m=matrix.size(); int n=matrix[0].size(); int loRow=0, hiRow= m-1; while(hiRow>=loRow){ int midRow = (hiRow+loRow)/2; if(matrix[midRow][0]>target){ hiRow = midRow-1; } else{ loRow = midRow+1; } } // cout << hiRow << " "<< loRow << endl; int hiCol=n-1; int loCol=0; if(hiRow<0)return false; while(hiCol>=loCol){ int midCol = (hiCol+loCol)/2; if(matrix[hiRow][midCol]>target){ hiCol = midCol-1; } else{ loCol = midCol+1; } } if(hiCol<0)return false; if(matrix[hiRow][hiCol]==target) return true; else return false; } };