content: package org.redquark.tutorials.leetcode;
  
  /**
   * @author Anirudh Sharma
   * <p>
   * Given two sorted arrays nums1 and nums2 of size m and n respectively,
   * return the median of the two sorted arrays.
   * <p>
   * Follow up: The overall run time complexity should be O(log (m+n)).
   * <p>
   * Constraints:
   * <p>
   * nums1.length == m
   * nums2.length == n
   * 0 <= m <= 1000
   * 0 <= n <= 1000
   * 1 <= m + n <= 2000
   * -10^6 <= nums1[i], nums2[i] <= 10^6
   */
  public class MedianOfTwoSortedArrays {
  
      /**
       * @param nums1 - first sorted array
       * @param nums2 - second sorted array
       * @return - median of two arrays
       */
      private static double findMedianSortedArrays(int[] nums1, int[] nums2) {
          // Check if num1 is smaller than num2
          // If not, then we will swap num1 with num2
          if (nums1.length > nums2.length) {
              return findMedianSortedArrays(nums2, nums1);
          }
          // Lengths of two arrays
          int m = nums1.length;
          int n = nums2.length;
          // Pointers for binary search
          int start = 0;
          int end = m;
          // Binary search starts from here
          while (start <= end) {
              // Partitions of both the array
              int partitionNums1 = (start + end) / 2;
              int partitionNums2 = (m + n + 1) / 2 - partitionNums1;
              // Edge cases
              // If there are no elements left on the left side after partition
              int maxLeftNums1 = partitionNums1 == 0 ? Integer.MIN_VALUE : nums1[partitionNums1 - 1];
              // If there are no elements left on the right side after partition
              int minRightNums1 = partitionNums1 == m ? Integer.MAX_VALUE : nums1[partitionNums1];
              // Similarly for nums2
              int maxLeftNums2 = partitionNums2 == 0 ? Integer.MIN_VALUE : nums2[partitionNums2 - 1];
              int minRightNums2 = partitionNums2 == n ? Integer.MAX_VALUE : nums2[partitionNums2];
              // Check if we have found the match
              if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1) {
                  // Check if the combined array is of even/odd length
                  if ((m + n) % 2 == 0) {
                      return (Math.max(maxLeftNums1, maxLeftNums2) + Math.min(minRightNums1, minRightNums2)) / 2.0;
                  } else {
                      return Math.max(maxLeftNums1, maxLeftNums2);
                  }
              }
              // If we are too far on the right, we need to go to left side
              else if (maxLeftNums1 > minRightNums2) {
                  end = partitionNums1 - 1;
              }
              // If we are too far on the left, we need to go to right side
              else {
                  start = partitionNums1 + 1;
              }
          }
          // If we reach here, it means the arrays are not sorted
          throw new IllegalArgumentException();
      }
  
      public static void main(String[] args) {
          int[] nums1 = new int[]{1, 3};
          int[] nums2 = new int[]{2};
          System.out.println(findMedianSortedArrays(nums1, nums2));
  
          nums1 = new int[]{1, 2};
          nums2 = new int[]{3, 4};
          System.out.println(findMedianSortedArrays(nums1, nums2));
  
          nums1 = new int[]{0, 0};
          nums2 = new int[]{0, 0};
          System.out.println(findMedianSortedArrays(nums1, nums2));
  
          nums1 = new int[]{};
          nums2 = new int[]{1};
          System.out.println(findMedianSortedArrays(nums1, nums2));
  
          nums1 = new int[]{2};
          nums2 = new int[]{};
          System.out.println(findMedianSortedArrays(nums1, nums2));
      }
  }
  