forked from Suman21/Interviewbit-Solution
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Search for a Range.cpp
54 lines (53 loc) · 951 Bytes
/
Search for a Range.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
vector<int> Solution::searchRange(const vector<int> &A, int B) {
int s=0,e=A.size(),f=0,m,l=0,r=0;
vector<int> ans;
if(A[A.size()-1]<B)
{
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
while(e>=s)
{
m=(s+e)/2;
if((A[m]==B && m==0) || (A[m]==B && A[m-1]!=B))
{
f=1;
l=m;
break;
}
else if(A[m]>=B)
{
e=m-1;
}
else
s=m+1;
}
s=0;
e=A.size();
if(f==0)
{
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
ans.push_back(m);
while(e>=s)
{
m=(s+e)/2;
if((A[m]==B && m==A.size()-1) || (A[m]==B && A[m+1]!=B))
{
f=1;
l=m;
break;
}
else if(A[m]>B)
{
e=m;
}
else
s=m+1;
}
ans.push_back(m);
return ans;
}