Tags： BinarySearch
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
public class Solution {
public int findkth(int A[], int startA, int endA, int B[], int startB, int endB, int k){
if(endA-startA > endB-startB){
return findkth(B, startB, endB, A, startA, endA, k);
}
if(endA <= startA){
return B[startB + k - 1];
}
if(k == 1){
return Math.min(A[startA], B[startB]);
}
int ia = Math.min(endA - startA, k / 2);
int ib = k - ia;
if(A[startA + ia - 1] < B[startB + ib - 1]){
return findkth(A, startA+ia, endA, B, startB, endB, ib);
}else if(A[startA + ia - 1] > B[startB + ib - 1]){
return findkth(A, startA, endA, B, startB+ib, endB, ia);
}else{
return A[startA + ia - 1];
}
}
public double findMedianSortedArrays(int A[], int B[]) {
int lenA = A.length;
int lenB = B.length;
if(((lenA + lenB)&1) == 0){
return (findkth(A, 0, lenA, B, 0, lenB, (lenA+lenB)/2) +
findkth(A, 0, lenA, B, 0, lenB, (lenA+lenB)/2+1))/2.0;
}else{
return findkth(A, 0, lenA, B, 0, lenB, (lenA+lenB+1)/2);
}
}
}
