Problem
I am trying to solve this InterviewBit question
https://www.interviewbit.com/problems/searchforarange/.
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+(highlow)/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[mid1]==b)
high=mid1;
else
return mid;
}
}
else if(a[mid]>b)
high=mid1;
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;
}
Solution
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 mainwhile
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 computea.size()  1
. This could be done once at the top of the function and bound to aconst
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.