-
Notifications
You must be signed in to change notification settings - Fork 31
/
Copy path4. Median of Two Sorted Arrays.c
147 lines (126 loc) · 3.59 KB
/
4. Median of Two Sorted Arrays.c
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
*/
int bs(int *n, int sz, int k) {
int i, j, m;
i = 0;
j = sz - 1;
while (i <= j) {
m = i + (j - i) / 2;
if (n[m] > k) {
j = m - 1;
} else {
i = m + 1;
}
}
return j; // this is the lastest one which is not greater than k
}
double bs2(int *n1, int sz1, int *n2, int sz2, int m, int m1) {
double d;
int i;
i = bs(n1, sz1, n2[0]); // search in first array
if (i >= m) { // median is in the first array
d = n1[m];
if (m1) {
if (i > m) {
d += n1[m + 1];
} else {
d += n2[0];
}
d /= 2;
}
} else if (i == sz1 - 1) { // median is in the second array
d = n2[m - i - 1];
if (m1) {
d += n2[m - i];
d /= 2;
}
} else { // reverse arrays and search again
d = bs2(n2, sz2, &n1[i + 1], sz1 - i - 1, m - i - 1, m1);
}
return d;
}
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
double d;
#if 0 // sliding & binary search
int i1_left = 0, i1_right = nums1Size;
int i1, i2;
if (nums1Size > nums2Size) { // make nums1 as a short array
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
}
// O(log(min(m, n)))
while (i1_left <= i1_right) {
i1 = i1_left + (i1_right - i1_left) / 2;
i2 = (nums1Size + nums2Size + 1) / 2 - i1;
if (i1 > 0 && nums1[i1 - 1] > nums2[i2]) {
i1_right = i1 - 1;
} else if (i1 < nums1Size && nums1[i1] < nums2[i2 - 1]) {
i1_left = i1 + 1;
} else {
// found it!
if (i1 == 0) d = nums2[i2 - 1];
else if (i2 == 0) d = nums1[i1 - 1];
else if (nums1[i1 - 1] > nums2[i2 - 1]) d = nums1[i1 - 1];
else d = nums2[i2 - 1];
if (((nums1Size + nums2Size) % 2) == 0) {
if (i2 == nums2Size) {
d = (d + nums1[i1]) / 2;
} else if (i1 == nums1Size) {
d = (d + nums2[i2]) / 2;
} else if (nums1[i1] < nums2[i2]) {
d = (d + nums1[i1]) / 2;
} else {
d = (d + nums2[i2]) / 2;
}
}
break;
}
}
#else // binary search 40+ms
int p1, p2;
p1 = (nums1Size + nums2Size - 1) / 2;
p2 = ((nums1Size + nums2Size) % 2) ? 0 : 1;
if (nums2Size == 0) {
d = nums1[p1];
if (p2) {
d += nums1[p1 + 1];
d /= 2;
}
return d;
}
if (nums1Size == 0) {
d = nums2[p1];
if (p2) {
d += nums2[p1 + 1];
d /= 2;
}
return d;
}
if (nums2[0] < nums1[0]) return bs2(nums2, nums2Size, nums1, nums1Size, p1, p2);
return bs2(nums1, nums1Size, nums2, nums2Size, p1, p2);
#endif
return d;
}
/*
Difficulty:Hard
Total Accepted:182.7K
Total Submissions:839.6K
Companies Google Zenefits Microsoft Apple Yahoo Dropbox Adobe
Related Topics Binary Search Array Divide and Conquer
*/