forked from striver79/SDESheet
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmedianOf2SortedArraysJava
35 lines (29 loc) · 1.17 KB
/
medianOf2SortedArraysJava
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
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums2.length < nums1.length) return findMedianSortedArrays(nums2, nums1);
int n1 = nums1.length;
int n2 = nums2.length;
int low = 0, high = n1;
while(low <= high) {
int cut1 = (low+high) >> 1;
int cut2 = (n1 + n2 + 1) / 2 - cut1;
int left1 = cut1 == 0 ? Integer.MIN_VALUE : nums1[cut1-1];
int left2 = cut2 == 0 ? Integer.MIN_VALUE : nums2[cut2-1];
int right1 = cut1 == n1 ? Integer.MAX_VALUE : nums1[cut1];
int right2 = cut2 == n2 ? Integer.MAX_VALUE : nums2[cut2];
if(left1 <= right2 && left2 <= right1) {
if( (n1 + n2) % 2 == 0 )
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
else
return Math.max(left1, left2);
}
else if(left1 > right2) {
high = cut1 - 1;
}
else {
low = cut1 + 1;
}
}
return 0.0;
}
}