-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMerge two sorted arrays of different sizes
43 lines (37 loc) · 1.21 KB
/
Merge two sorted arrays of different sizes
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
Question : https://leetcode.com/problems/median-of-two-sorted-arrays/
Tutorial : https://youtu.be/NTop3VTjmxk
Editorial : https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation
/* Binary Search */
class Solution {
public:
double median(vector<int>&a,vector<int>&b){
int m=a.size();
int n=b.size();
if(m>n)
return median(b,a);
int l=0,r=m;
while(l<=r){
int cut1 = l+(r-l)/2;
int cut2 = (m+n+1)/2-cut1;
int l1 =(cut1==0)?INT_MIN:a[cut1-1];
int r1 =(cut1==m)?INT_MAX:a[cut1];
int l2 =(cut2==0)?INT_MIN:b[cut2-1];
int r2 =(cut2==n)?INT_MAX:b[cut2];
if(l1<=r2 && l2<=r1){
if((m+n)%2==0)
return (double)(max(l1,l2)+min(r1,r2))/2;
else
return (double)(max(l1,l2));
}else if(l1>r2)
r=cut1-1;
else
l=cut1+1;
}
return -1.0;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
double ans;
ans=median(nums1,nums2);
return ans;
}
};