# 4ms C++ solution based on binary search

• ``````class Solution {
public:
string Parse(int d)
{
char buf[30] = {0};
sprintf(buf, "%d",d);
string ret(buf);
return ret;
}

string Parse(int d1, int d2)
{
char buf[30] = {0};
sprintf(buf, "%d", d1);
string tmp(buf);
memset(buf, 0, 30);
tmp.append("->");
sprintf(buf, "%d", d2);
string tmp2(buf);
tmp.append(tmp2);
return tmp;
}

int findSection(int A[], int n, int v)
{
int start = 0;
int end = n - 1;

if(n<=0) return -1;

while (1)
{

int m = (start + end) / 2;

if (A[m] == v) return m;

if (v<A[m])
{
if (m == 0) return 0;
if (v > A[m - 1]) return m;
else end = m - 1;
}

if (v>A[m])
{
if (m == n - 1) return n - 1;
if (v<A[m + 1]) return m + 1;
start = m + 1;
}
}
}

vector<string> findMissingRanges(int A[], int n, int lower, int upper)
{
int p = findSection(A, n, lower);
int q = findSection(A, n, upper);

vector<string> ret;
char buf[30] = {0};

if(p==-1)
{
if(upper==lower)
{
ret.push_back(Parse(lower));
return ret;
}
else
{
ret.push_back(Parse(lower, upper));
return ret;
}
}

if (p > q) return ret;
int i = p;

if (A[p] - lower>0)
{
if (A[p] - lower == 1)
{
ret.push_back(Parse(lower));
}
else
{
ret.push_back(Parse(lower, A[p]-1));
}
}

i++;
while (i<=q)
{
if (A[i] - A[i-1]>1)
{
if (A[i] - A[i - 1] == 2)
{
ret.push_back(Parse(A[i - 1] + 1));
}
else
{
ret.push_back(Parse(A[i - 1] + 1, A[i]-1));
}
}

i++;
}

if (upper-A[q]>0)
{
if (upper - A[q] == 1)
{
ret.push_back(Parse(upper));
}
else
{
ret.push_back(Parse(A[q] + 1, upper));
}
}

return ret;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.