# Share my O(log(min(m,n)) solution with explanation

• Thanks, I found something from your reference:
'''public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double median1 = 0;
double median2 = 0;
double median = 0;
Arrays.sort(array1);
Arrays.sort(array2);
if (array1.length % 2 == 0) {
median1 = ((double) array1[array1.length / 2] + (double) array1[array1.length / 2 - 1]) / 2;
} else {
median1 = (double) array1[array1.length / 2];
}
if (array2.length % 2 == 0) {
median2 = ((double) array2[array2.length / 2] + (double) array2[array2.length / 2 - 1]) / 2;
} else {
median2 = (double) array2[array2.length / 2];
}
median = (median1 + median2) / 2;
return median;
}
}'''

• class Solution {

``````public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j-1] > A[i]){
iMin = iMin + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = iMax - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }

return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
``````

}

1,why the condition is :

i < iMax && B[j-1] > A[i]，
i > iMin && A[i-1] > B[j])

why i<iMax and i>iMin

2,why:

iMin = iMin + 1; // i is too small ????
iMax = iMax - 1; // i is too big ????
why not iMin=i+1? and iMax=i-1?

• THX for sharing your brilliant idea, rewrite in C++.

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if(m > n) return findMedianSortedArrays(nums2, nums1);
int lo = 0, hi = m, mid = (m + n + 1)/2;
while(lo <= hi){
int i = (lo + hi)/2;
int j = mid - i;
if(i < m && nums2[j - 1] > nums1[i])
lo = i + 1;
else if(i > 0  && nums1[i - 1] > nums2[j])
hi = i - 1;
else{
int maxLeft = (i == 0) ? nums2[j - 1] : (j == 0) ? nums1[i - 1] : max(nums1[i - 1], nums2[j - 1]);
int minRight = (i == m) ? nums2[j] : (j == n) ? nums1[i] : min(nums1[i], nums2[j]);
return (m + n) % 2 ? maxLeft : (maxLeft + minRight) / 2.0;
}
}
}
};
``````

• JAVA Solution

``````public double findMedianSortedArrays(int[] A, int[] B){
int m = A.length;
int n = B.length;
if(m > n){
return findMedianSortedArrays(B, A);
}
int minIndex = 0, maxIndex = m, halfLen = (m + n + 1) / 2;
int maxLeft, minRight;
while(minIndex <= maxIndex){
int i = (minIndex + maxIndex) / 2;
int j = halfLen - i;
if(i < m && B[j - 1] > A[i]){
minIndex = i + 1;
} else if(i > 0 && A[i - 1] > B[j]){
maxIndex = i - 1;
} else{
if(i == 0){
maxLeft = B[j - 1];
} else if(j == 0){
maxLeft = A[i - 1];
} else{
maxLeft = Math.max(A[i - 1], B[j - 1]);
}
if((m + n) % 2 == 1){
return maxLeft;
}
if(i == m){
minRight = B[j];
} else if(j == n){
minRight = A[i];
} else{
minRight = Math.min(A[i], B[j]);
}
return (maxLeft + minRight) / 2.0;
}
}
return 0;
}
``````

• ``````public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[] buf = new int[len1 + len2];
int i = 0, j = 0, k = 0;
double median = 0;
while (i < len1 && j < len2) {
if (nums1[i] < nums2[j]) {
buf[k++] = nums1[i++];
} else {
buf[k++] = nums2[j++];
}
}
while(i < len1){
buf[k++] = nums1[i++];
}
while(j < len2){
buf[k++] = nums2[j++];
}
int len = buf.length;
if(len % 2 == 0){
median = (buf[len / 2] + buf[len / 2 - 1]) / 2.0;
}else{
median = buf[len / 2];
}
return median;
}
``````

I think it is easy to understand !

• @jialic You'd better review binary search and time complexity part of textbook first before you go through this solution. Six upvotes of your post mean you mislead at least six people about how this solution works.

• @jialic It's wrong. Don't mislead others. Since i depends on imin and imax. It seems we do the binary search on the small array. The complexity should be O(log(min(m, n)))

• i wonder why (m+n+1)/2 is used instead of (m+n)/2

• ``````        int len1 = nums1.length;
int len2 = nums2.length;
int len = len1 + len2;
int med = len/2+1;
//System.out.println(med);
ArrayList<Integer> list = new ArrayList<>();
int i=0, j=0;
while(i+j < med){
if (i<len1 && j<len2)
{
if (nums1[i] < nums2[j])
{
i++;
} else
{
j++;
}
}
else if (i == len1){
for (int k=j; k<len2; k++)
break;
}
else if (j == len2){
for (int k=i; k<len1; k++)
break;
}
}
//for(int k : list)
//System.out.println(k);
if ((len&1) != 0)
return list.get(med-1);
else
return (list.get(med-2)+list.get(med-1))/2.0;
}
``````

• Clear concise explanation. Thank you.

• @MissMary
Hi,

Could you explain why, i + j = m - i + n - j + 1 ?
or rather why do we do a "+1" in this equation.?

• @MissMary but in java code, iMin = iMin + 1 ; this is not binary search.

• The judging seems to have a problem on this one. The following is the straightforward brute force O(n+m) solution, but it passed and not only that, was faster than 91.78% of swift submissions!

``````class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {

let nums = mergeSortedArrs(nums1, nums2)
//printArr(nums)
//print("nums1[\(i1)]=\(nums1[i1]) nums2[\(i2)]=\(nums2[i2])")

let N = nums.count
let medianIndex = N / 2

if N % 2 == 1 { // odd case
return Double(nums[medianIndex])
} else { // even case
return Double(nums[medianIndex-1] + nums[medianIndex])/2
}

}

func printArr(_ nums: [Int]) -> Void {

print("nums = [", terminator: "")
for i in 0..<nums.count {
if (i == nums.count - 1) {
print("\(i): \(nums[i])", terminator: "")
} else {
print("\(i): \(nums[i]), ", terminator: "")
}
}
print("]")
}

private func mergeSortedArrs(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var nums = [Int]()
var i1 = 0
var i2 = 0
let N1 = nums1.count
let N2 = nums2.count
let N = N1 + N2
while (i1+i2 < N) {
if (i1 >= N1) {
nums.append(nums2[i2])
i2 += 1
} else if (i2 >= N2) {
nums.append(nums1[i1])
i1 += 1
} else {
if (nums1[i1] <= nums2[i2]) {
nums.append(nums1[i1])
i1 += 1
} else {
nums.append(nums2[i2])
i2 += 1
}
}
}

return nums
}
}
``````

• Great！How do you think of it？How do you think of QSort？

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