# Time complexity n(logM*logN) solution

• /**
* 0 1 2 3 4 5 6 7
* A 1 3 6
* B 2 4 5 7 8 9 10 11
*
* Length of A is m and B is n. If merge array A and B, the median element is at (m+n)/2.
* If we can find one element that its index in A plus its index in B is (m+n)/2. It is the right element.
* eg: 6 is the median element and (m+n)/2 is 5, it is in 2nd place of A and 3rd place of B.
*
* The median element is either in A or B. Let's assume it is in A, we can do following step to try to find it.
* 1. Take middle element from A, so the index from A is (low+high)/2 as middle. (At first, low is 0 and high is m).
* 2. Do binary search on element A[middle] in array B to get the index from B as indexB.
* 1) If middle + indexB equals (m+n)/2, we find the right element.
* 2) If middle + indexB less than (m+2)/2, we need a bigger element and set low as middle.
* Else we need a smaller element ans set high as middle. Repeat step 1 and 2.
*
* If we don't find the element, the element is must in B. we can do same for array B.
*
* There are 2 loops here, the first loop always take middle element so time complexity is O(logm),
* the second loop is do binary search so time complexity is O(logn). The final complexity is
* O(logm*logn)
*
* If m+n is odd, find index (m+n)/2 among array A and B; else find index (m+n)/2 and ((m+n)/2)-1
*
* odd:
* targetIndex = (m+n)/2
* lowA = 0
* highA = A.length
* for midIndex <- (lowA+highA)/2
* indexInB = binarySearch A[mid] in B[n]
* if midIndex+indexInB = targetIndex
* return A[midIndex]
* if midIndex+indexInB < targetIndex
* lowIndex = midIndex + 1
* else
* highIndex = midIndex
*
*
*/

``````public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;

if (n % 2 == 1) {
int t = find(nums1, nums2, n/2, true);
return  t == -1 ? find(nums2, nums1, n/2, false) : t;
} else {
int t1 = find(nums1, nums2, n/2 - 1, true);
int t2 = find(nums1, nums2, n/2, true);

if (t1 == -1) {
t1 = find(nums2, nums1, n/2 - 1, false);
}
if (t2 == -1) {
t2 = find(nums2, nums1, n/2, false);
}

return (t1 + t2) / 2.0;
}
}

private int find(int[] nums1, int[] nums2, int targetIndex, boolean flag) {
int low1 = 0;
int high1 = nums1.length;

while (low1 < high1) {
int middle1 = low1 + (high1-low1)/2;

int index2 = binarySearch(nums1[middle1], nums2, flag);

if (middle1 + index2 == targetIndex) {
return nums1[middle1];
}

if (middle1 + index2 < targetIndex) {
low1 = middle1 + 1;
} else {
high1 = middle1;
}
}

return -1;
}

private int binarySearch(int target, int[] nums, boolean flag) {
int low = 0;
int high = nums.length;

while (low < high) {
int middle = low + (high-low)/2;

if ((target > nums[middle] && flag) || (target >= nums[middle] && !flag)) {
low = middle + 1;
} else {
high = middle;
}
}

return low;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.