Finding the upper and lower bound using binary search

Question

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;
}

Answer 1

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.