-
Notifications
You must be signed in to change notification settings - Fork 0
/
Median of an array
42 lines (35 loc) · 930 Bytes
/
Median of an array
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
double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
if(B.size()<A.size())
{
return findMedianSortedArrays(B,A);
}
int n1 = A.size(), n2 = B.size();
int low=0;
int high=n1;
while(low<=high)
{
int cut1=(low+high)/2;
int cut2=(n1+n2+1)/2-cut1;
double left1=cut1==0?INT_MIN : A[cut1-1];
double left2=cut2==0?INT_MIN : B[cut2-1];
double right1=cut1==n1?INT_MAX : A[cut1];
double right2=cut2==n2?INT_MAX : B[cut2];
if(left1<=right2 && left2<=right1)
{
if((n1+n2)%2==0){
return (max(left1,left2)+min(right1,right2))/2;
}
else
return max(left1,left2);
}
else if(left1>right2)
{
high=cut1-1;
}
else
{
low=cut1+1;
}
}
return 0;
}