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