# Median of Two sorted arrays - Code

## Median of Two sorted arrays - Code

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Code

``````int findMedian(int arr[], int n, int brr[], int m){
// code here
int begin1 = 0 ; int end1 = n;
while(begin1<=end1){
int i1 = (begin1+end1)/2;
int i2 = (n+m+1)/2 - i1;

int min1 = (i1==n) ? INT_MAX : arr[i1];
int max1 = (i1==0) ? INT_MIN : arr[i1-1];

int min2 = (i2==m) ? INT_MAX : brr[i2];
int max2 = (i2==0) ? INT_MIN : brr[i2-1];

if((max1<=min2) && (max2<=min1) ){
if((n+m)%2==0){
return ((double) (max(max1,max2) + min(min1, min2)) / 2) ;
}else{
return ((double) max(max1, max2));
}
}
else if(max1>min2){
end1 = i1-1;
}else{
begin1 = i1+1;
}
}
}``````

Explanation

1. We will divide the individual arrays in two part using int i1 = (begin1+end1)/2;
2.  int i2 = (n+m+1)/2 - i1;
3. After this we will assign min1 and max1 in i1, min 1 will be the right part and max 2 will be the left part. Similarly with i2, min2 right part and max2 left part.
4. After this we will check if min1 > max2 and min2>max1 then use this formula max(max1,max2) + min(min1, min2)) / 2
5. Else change the i1 with i1 + 1 and i2 with i2-1 to arrive at this condition min1 > max2 and min2>max1.
6. So this is how we can do this job.

For explanation you can refer following videos:

English
https://youtu.be/NTop3VTjmxk

Hindi
https://youtu.be/ws98ud9uxl4