My solution is O( log(m) + log(n) ) but it shows TLE. Can it be better?


#1

My solution is O( log(m) + log(n) ) but it shows TLE. Can it be better?


#2

TLE is not due to your complexity.
Check your recursion carefully.
I submitted O(m+log(n)) and it worked.


#3

It can be directly done in O(mlogn) and is accepted.
Yes it can also be done in O(logmn) which you have done(most efficient one). There must be some other problem which is responsible for TLE.


#4

O(log(m) + log(n)) is the most efficient one. (Check whether l + 1 == r. Its common cause of TLE in binary search)


#5

int binSearch(vector &V, int low,int high,int key){
int mid=low+(high-low)/2;
while(low<=high){
if(V[mid]==key) return 1;
else if(V[mid]<key) high=mid-1;
else low=mid-1;
}
return 0;
}
int Solution::searchMatrix(vector<vector > &A, int B) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int m=A.size(),n=A[0].size();//m = no of rows, n= no of cols
bool flag=false;
for(int i=0;i<m;i++){
if(B>=A[i][0]&&B<=A[i][n-1]){
if(binSearch(A[i],0,n-1,B)){flag=true; break;}
}
else if(i>0&&B>A[i-1][n-1]&&B<A[i][0]){break;}
}
if(flag==true) return 1;
else return 0;
}
This is my code. It is running in O(m logn) but showing time limit exceeded for 10x4 matrix in which target is not present. Anyone with suggestions to optimize the code??


#6

I guess below code has problem

if(V[mid]==key) return 1;
else if(V[mid]<key) high=mid-1;
else low=mid-1;


Low should be mid+1;