Median of Two Sorted Arrays

While working on leetcode I came across the first question marked "Hard". It goes like this:

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)).

The first part of this prompt is fairly straightforward. The second part... not so much. To get a quick solution, I did the first thing that came to my mind: Concatenate the arrays, sort them, find the median for an odd length array or an even length array.

var findMedianSortedArrays = function(nums1, nums2) {
    
    let nums = nums1.concat(nums2).sort(sortFunction)

    let isOdd = nums.length % 2
    
    if(isOdd){
        return nums[Math.floor(nums.length/2)]
    }

    return (nums[Math.floor(nums.length/2)-1] + nums[Math.floor(nums.length/2)])/2
};

var sortFunction = function (a, b){
    return a - b
}

This solves the problem, but not with the required run time complexity. To reduce the runtime complexity, we have to take another approach, and the key to that approach is that the given arrays are sorted. This means if we're searching for values in those arrays, we don't have to check every value - which would be O(N) and too slow to satisfy the problem statement. We can instead use a binary search approach. From a high level, we look at each of the arrays and partition them in half and check to see if the values on either side of the partition are correctly split THere are a couple important numbers we'll use to break the arrays into partitions. The first is the combined length. In one sorted array, the median is the middle value or the average of the two middle values. If we're looking for the median in two arrays instead of one, we can think about finding a middle point in each array. If we find a middle point in both arrays, to partition those arrays like binary search requires, the two left sides of both arrays will have half as many elements as the combined length. Here's the algorithm I learned about from Neetcode - https://www.youtube.com/watch?v=q6IEA26hvXc&t=764s

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(A, B) {
    if( B.length < A.length){
        let temp = A
        A = B
        B = temp
    }
    
    let left = 0
    let right = A.length - 1
    let total = A.length + B.length
    let half = Math.floor(total / 2)
    
    while(true){
        let i = Math.floor((left + right) / 2)
        let j = half - i - 2
        
        let Aleft = i >= 0 ? A[i] : -Infinity
        let Aright = (i + 1) < A.length ? A[i + 1] : Infinity
        
        let Bleft = j >= 0 ? B[j] : -Infinity
        let Bright = (j + 1) < B.length ? B[j + 1] : Infinity
                
        if(Aleft <= Bright && Bleft <= Aright){
            if (total % 2 === 0){
                return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2
            }
            return Math.min(Aright, Bright)
        }
        
        if(Aleft > Bright) {
            right = i - 1
        } else {
            left = i + 1
        }
    }
};

And here's the algorithm for annotated for further understanding:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(A, B) {
    //Take the smallest of the two arrays
    //This allows us to binary search the smaller of the two, saving us some time
    //Once we have the A
    if( B.length < A.length){
        let temp = A
        A = B
        B = temp
    }
    
    let left = 0
    let right = A.length - 1
    let total = A.length + B.length
    let half = Math.floor(total / 2) //half the total, used to see how many to each side of our partitions
    let i //index we use to look for the middle of the A array
    let j //index we use to look for the middle of the B array
    let Aleft //left side of the partition on the A array
    let Aright //right side of the partition on the A array
    let Bleft //left side of the partition on the B array
    let Bright //right side of the partition on the B array
    
    while(true){
		//index of the midpoint of A
        i = Math.floor((left + right) / 2)
		//index of the midpoint of B
        j = half - i - 2
        
		//Here were finding two values, and essentially seeing if there is a valid index at that point, or if we go 
		//too far, were setting the value to infinity. That means weve reached the edge of our sorted array and cant
		//go any farther
		//Aleft is the left side of the middle of the A array
        Aleft = i >= 0 ? A[i] : -Infinity
		//Aright is the right side of the middle of the A array, adjacent to Aleft
        Aright = (i + 1) < A.length ? A[i + 1] : Infinity
        
		//Bleft is the left side of the middle of the B array
        Bleft = j >= 0 ? B[j] : -Infinity
		//Bright is the right side of the middle of the B array
        Bright = (j + 1) < B.length ? B[j + 1] : Infinity
                                   
		//So these two partitions together are what the left side of a partitioned combined array would be. and if know that,
		//we can just find the middle and get the median now
                
		//If this condition is true, then we our partitions are correct and we have found our median. 
        if(Aleft <= Bright && Bleft <= Aright){
            if (total % 2 === 0){
                return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2
            }
            return Math.min(Aright, Bright)
        }
        
                                              
		//if Aleft is greater than Bright, our partitions are incorrect
		//In a sorted array this would mean that the right side partition has a number greater then the left parti
		//Reminder that these are not indexes, these are the values left and right most in the sorted arrays
		//if we havent found our median here, then the we need to change our search indexes	
		//Aleft is too big, our A array partition needs to be reduced
        if(Aleft > Bright) {
            right = i - 1
        } else {
      //Otherwise we increase our A array
            left = i + 1
        }
    }
};