Hint: First binary search to locate row index, then binary search in row to check if element is present


#1

int Solution::searchMatrix(vector<vector > &A, int B) {
if(A[0][0]==B) return 1;
if(A[A.size()-1][A[0].size()-1]==B) return 1;
if(A[0][0]>B) return 0;
if(A[A.size()-1][A[0].size()-1]<B) return 0;

int l=0, r=A.size()-1;
int j=A[0].size()-1;

// finding row index by binary search
while(l<r){
    int mid = (r-l)/2 +l;
    if(A[mid][j]==B) return 1;
    else if(A[mid][j]>B) r = mid;
    else l = mid+1;
}
int x = l;
// check if element exists in that row by bunary search
l=0, r=j;
while(l<r){
    int mid = (r-l)/2 + l;
    if(A[x][mid]==B) return 1;
    else if(A[x][mid]<B) l = mid+1;
    else r=mid;
}

return 0;

}