Median of Two Sorted Arrays

You are given two sorted arrays, nums1 and nums2, with sizes m and n respectively. Your task is to find the median of the two sorted arrays. The overall runtime complexity of your solution should be O(log (m+n)).

Here are two examples to illustrate the problem:

Example 1: nums1 = [1, 3] nums2 = [2] The median of nums1 and nums2 is 2.0.

Example 2: nums1 = [1, 2] nums2 = [3, 4] The median of nums1 and nums2 is (2 + 3)/2 = 2.5.

To solve this problem efficiently, you can use a binary search-based approach. Since both arrays are sorted, you can compare the medians of the two arrays and make decisions based on the comparisons to narrow down the search space.

Here’s an outline of the algorithm:

1. Find the smaller array between nums1 and nums2, and assign it to a variable called “smaller”. Also, find the larger array and assign it to a variable called “larger”.
2. Initialize two pointers, “left” and “right”, for the smaller array “smaller”. Set “left” to 0 and “right” to the length of “smaller” array.
3. Perform a binary search on the “smaller” array while updating “left” and “right” pointers until “left” is less than or equal to “right”.
4. Calculate the partition points “partitionX” and “partitionY” in the “smaller” and “larger” arrays respectively, based on the “left” and “right” pointers.
5. Compare the elements at “partitionX-1” and “partitionX” in the “smaller” array, and similarly compare the elements at “partitionY-1” and “partitionY” in the “larger” array.
6. Based on the comparisons, adjust the “left” and “right” pointers to narrow down the search space in the “smaller” array.
7. Repeat steps 4–6 until you find the correct partition points such that the elements on both sides of the partition points satisfy the median condition (i.e., all elements on the left side are smaller than all elements on the right side).
8. Once you find the correct partition points, calculate the median based on the elements at the partition points and return the result.
9. If the “smaller” array has an even number of elements, take the average of the maximum of the elements on the left side of the partition points and the minimum of the elements on the right side. If the “smaller” array has an odd number of elements, return the element at the partition point as the median.

By using the binary search-based approach, you can achieve the desired runtime complexity of O(log (m+n)).

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int counter=0;
    int flag1=0;
    int flag2=0;
    int target=(nums1Size+nums2Size)/2;
    int mid=0;
 
    if((nums1Size+nums2Size)&0x01)
      target++;
 
    //check if nums1 or nums2 is null
    if(nums1Size==0)
    {
        if(nums2Size==1)
          return nums2[0];
 
        if((nums1Size+nums2Size)&0x01)
          return nums2[target-1];
        else
          return ((double)nums2[target]+(double)nums2[target-1])/2;
    }
 
    if(nums2Size==0)
    {
        if(nums1Size==1)
          return nums1[0];
 
        if((nums1Size+nums2Size)&0x01)
          return nums1[target-1];
        else
          return ((double)nums1[target]+(double)nums1[target-1])/2;
    }
 
    printf("target:%d\n",target);
 
    while(counter!=target)
    {
        counter++;
        if(flag1>=nums1Size)
        {
            mid=nums2[flag2];
            flag2++;
            continue;
        }
        if(flag2>=nums2Size)
        {
            mid=nums1[flag1];
            flag1++;
            continue;
        }
 
        if(nums1[flag1]>nums2[flag2])
        {
            mid=nums2[flag2];
            flag2++;
        }else
        {
            mid=nums1[flag1];
            flag1++;
        }
    }
 
    if((nums1Size+nums2Size)&0x01)
       return mid;
    else
    {
        if(flag1 == nums1Size)
          return ((double)mid+(double)nums2[flag2])/2;
        if(flag2 == nums2Size)
          return ((double)mid+(double)nums1[flag1])/2;
 
        if(nums1[flag1]>nums2[flag2])
        {
            return ((double)mid+(double)nums2[flag2])/2;
        }else
        {
            return ((double)mid+(double)nums1[flag1])/2;
        }
    }
}