#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/median-of-two-sorted-arrays-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/median-of-two-sorted-arrays-implementation

Repovive

Median of Two Sorted Arrays - Implementation - Binary Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Median of Two Sorted Arrays - Implementation

Here is the implementation:

function findMedianSortedArrays(nums1, nums2):
    if nums1.length > nums2.length:
        swap(nums1, nums2)

    m = nums1.length, n = nums2.length
    left = 0, right = m
    half = (m + n + 1) / 2

    while left <= right:
        i = (left + right) / 2
        j = half - i

        left1 = nums1[i-1] if i > 0 else -INF
        right1 = nums1[i] if i < m else +INF
        left2 = nums2[j-1] if j > 0 else -INF
        right2 = nums2[j] if j < n else +INF

        if left1 <= right2 and left2 <= right1:
            if (m + n) is odd:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        else if left1 > right2:
            right = i - 1
        else:
            left = i + 1

$O(\log(\min(m, n)))$ time, $O(1)$ space (excluding input).