# Median of Two Sorted Arrays

This page explains Java solution to problem `Median of Two Sorted Arrays` using `Binary Search` algorithm.

## Problem Statement

Given two sorted arrays `A` and `B` of size `m` and `n` respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be `O(log (m+n))`.

Example 1:

Input: A = [1,3], B = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2

Example 2:

Input: A = [1,2], B = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class MedianOfTwoSortedArrays {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;

if(m > n) return findMedianSortedArrays(B, A);

int lo = 0;
int hi = m;
/**
We do + 1 here to total length so that we get extra element on the left hand side
And we can return mid in case total number of elements are odd
*/
int halfOfTotalElements = (m + n + 1) / 2;
while(lo <= hi) {
int midLeft = lo + (hi - lo) / 2;
int midLeftA = midLeft == 0 ? Integer.MIN_VALUE : A[midLeft - 1];
int midRightA = midLeft == m ? Integer.MAX_VALUE : A[midLeft];

int midRight = halfOfTotalElements - midLeft;
int midLeftB = midRight == 0 ? Integer.MIN_VALUE : B[midRight - 1];
int midRightB = midRight == n ? Integer.MAX_VALUE : B[midRight];

if(midLeftA > midRightB) {
hi = midLeft - 1;
}
else if(midLeftB > midRightA) {
lo = midLeft + 1;
}
else {
midLeft = Math.max(midLeftA, midLeftB);
midRight = Math.min(midRightA, midRightB);
if((m + n) % 2 == 0) return (midLeft + midRight) / 2.0;
else return midLeft;
}
}
return -1;
}
}
``````

O(log(m + n))

O(1)