Why my code is showing TLE? can anyone explain


#1

int binarySearch(vector<vector> A, int i, int j_low, int j_high, int x){

while(j_low <= j_high){
    
    int j_mid = (j_low+j_high)/2;
    
    if(A[i][j_mid] == x)
        return 1;
    
    else if(A[i][j_mid] > x)
        j_high = j_mid-1;
        
    else
        j_low = j_mid+1;
    
    
}

return 0;

}

int Solution::searchMatrix(vector<vector > &A, int x) {

int m = A.size();
int n = A[0].size();


if(m == 1)
    return binarySearch(A, 0, 0, n-1, x);

int i_low=0, i_high=m-1, j_mid=n/2;

while((i_low+1) < i_high){
    
    int i_mid = (i_low+i_high)/2;
    
    if(A[i_mid][j_mid] == x)
        return 1;
    
    else if(A[i_mid][j_mid] > x)
        i_high = i_mid;
    else
        i_low = i_mid;
    
}

if(A[i_low][j_mid] == x)
    return 1;

else if(A[i_low+1][j_mid] == x)
    return 1;

else if(x <= A[i_low][j_mid-1])
    return binarySearch(A, i_low, 0, j_mid-1, x);
else if(x >= A[i_low][j_mid+1] && x <= A[i_low][n-1])
    return binarySearch(A, i_low, j_mid+1, n-1, x);
    
else if(x <= A[i_low+1][j_mid-1])
    return binarySearch(A, i_low+1, 0, j_mid-1, x);
else
    return binarySearch(A, i_low+1, j_mid+1, n-1, x);

}


#2

I don’t think you’re getting the main idea here. Don’t search for B in every row. It can be present in one of the rows which can be determined using the idea that

last element of previous row is smaller then first element of current row

So, first search for that row and then do a binary search on that row.
To help you, the following code can get you the row you’ve to search on
for(row = 0; row < A.size(); row++){ if (B <= A[row].back()) break; }