Median of Two Sorted Arrays

LeetCode Q 4 - Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Solution

This solution is following the idea in Tushar’s Youtube video. This video provides a quite clear and comprehensive description of the solution.
You can find this video here.

Code:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	if (nums1.length > nums2.length) return findMedianSortedArrays(nums1, nums2);

	int len1 = num1.length, len2 = num2.length;
	int left = 0, right = len1;
	while (left <= right) {
		int partitionX = (left + right) / 2;
		int partitionY = (len1 + len2 + 1) / 2 - partitionX;

		int leftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX - 1];
		int leftY = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY - 1];

		int rightX = partitionX == len1 ? Integer.MAX_VALUE : nums1[partitionX];
		int rightY = partitionY == len2 ? Integer.MAX_VALUE : nums2[partitionY];

		if (leftX <= rightY && leftY <= rightX) {
			if ((len1 + len2) % 2 = 1)
				return Math.max(leftX, leftY);
			else
				return (Math.max(leftX, leftY) + Math.min(rightX, rightY)) / 2.0;
		} else if (leftX > rightY) {
			right = partitionX - 1;
		} else {
			left = partitionX + 1;
		}
	}
	return 0;
}