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) {
if(i==j) return to_string(i);
else return to_string(i) + "->" + to_string(j);
}
int lower_bound(int A[], int i, int j, int target) {
while(i < j) {
int m = i+(j-i)/2;
if(target > A[m]) i=m+1;
else j=m;
}
return j;
}
```