Test H1

Partition the smaller array (let's say A) at a midpoint i. Based on the total number of elements, a corresponding partition point j is determined in the other array (B).

The goal is to find partitions where:

• Every element in the left partition of A is less than or equal to every element in the right partition of B.
• Every element in the left partition of B is less than or equal to every element in the right partition of A.

# Initialize pointers for binary search
l, r = 0, len(A) - 1

while True:
    i = (l + r) // 2
    j = half - i - 2

Compare the elements at the boundaries of the partitions (Aleft, Aright, Bleft, Bright). If the partitions are incorrect, adjust the binary search range.

• If Aleft > Bright, it means the partition in A is too large. Adjust by moving the right pointer: r = i - 1.
• If Bleft > Aright, the partition in A is too small. Adjust by moving the left pointer: l = i + 1.

    if Aleft <= Bright and Bleft <= Aright:
        # Correct partition found
        break
    elif Aleft > Bright:
        r = i - 1
    else:
        l = i + 1

Once the correct partitions are found, calculate the median.

• If the total number of elements is odd, the median is the minimum of the first elements in the right partitions of A and B.
• If the total number of elements is even, the median is the average of the maximum element from the left partitions and the minimum element from the right partitions.

# For odd number of elements
if total % 2:
    return min(Aright, Bright)

# For even number of elements
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2