# Share my c++ sol (binary search)

• I used binary to search for the first element A[i] that satisfies A[i] >= lower (like the std::lower_bound()). By definition, A[i-1] < lower and we can thus totally forget about anything from 0~i-1. Note that we will need to push back the range [lower,A[i]-1] if A[i] > lower.

Then again use binary search to search for the first element A[j] that satisfies A[j] >= upper. So we will have A[j-1] < upper. (Note that the lower_bound function works in such a way the if the last/largest element A[n-1] is less than upper than it outputs n-1. So you will need to check if it is j or j-1 that should be used as a upper bound in the following linear finding missing ranges)

Now we know that

lower <= A[i] <= A[j-1] (or A[j]) <= upper

so we can do linear search for missing ranges in this block.

``````vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
vector<string> result;
if(n==0 || lower > A[n-1] || upper < A[0])
return {getRange(lower,upper)};

int start = lower_bound(A,0,n-1,lower);
if(lower < A[start]) result.push_back(getRange(lower,A[start]-1));
int end = lower_bound(A,start,n-1,upper);
if(upper <= A[end]) end--;
for(int i=start; i<end; i++) {
if(i+1>end) break;
if(A[i+1]-A[i]>1) result.push_back(getRange(A[i]+1,A[i+1]-1));
}
if(upper > A[end]) result.push_back(getRange(A[end]+1,upper));
return result;
}
``````

The helper functions:

``````string getRange(int i, int j) {