5
\$\begingroup\$

I am trying to solve this InterviewBit question https://www.interviewbit.com/problems/search-for-a-range/.

My code for this seems to be working properly and it does give me the correct answers on my IDE and on all the sample test cases online but it gives me a TLE on the online judge. It runs in O(log n) time, just a variation of simple binary search.

I am trying to understand what aspect of my code could be made more efficient and faster.

Here's my code:

int findBound(vector<int> a, int b, bool lower){
int low=0, high=a.size()-1, mid;
while(low<=high){
    mid=low+(high-low)/2;
    if(a[mid]==b){
        if(lower){
            if((mid != (a.size()-1)) && a[mid+1]==b)
                low=mid+1;
            else
                return mid;
        }
        else{
            if(mid != 0 && a[mid-1]==b)
                high=mid-1;
            else
                return mid;
        }
    }
    else if(a[mid]>b)
        high=mid-1;
    else if(a[mid]<b)
        low=mid+1;
}
return -1;
}

vector<int> Solution::searchRange(const vector<int> &A, int B) {
    vector<int> ans(2);
    ans[0]=findBound(A, B, true);
    ans[1]=findBound(A, B, false);
    return ans;
}
\$\endgroup\$
8
\$\begingroup\$

I am trying to understand what aspect of my code could be made more efficient and faster.

First, the low hanging fruits...

  • You unnecessarily copy the sequence of integers when passing it to findBound:

    int findBound(vector<int> a, int b, bool lower)
    

    should be

    int findBound(const vector<int>& a, int b, bool lower)
    
  • You dispatch on the bool lower flag in every iteration of the main while-loop:

    if(lower) {
       /* ... */
    } else {
       /* ... */
    }
    

    Consider implementing two separate functions for the starting and one for the end index of the range.

  • In one of the if-conditions in the middle of the main loop, you compute a.size() - 1. This could be done once at the top of the function and bound to a const-qualified variable. No need to evaluate this in every iteration.

Now, the crucial step...

  • You are doing unnecessary work when comparing values. The very first if-condition,

    if(a[mid]==b) { // ...
    

    tests for the branch with the least likelihood. Instead, check for a[mid] < b and nothing more. If you're wondering how this can be sufficient, check out this part of Sean Parent's Pacific C++ talk from 2018.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.