The tell: Two sorted arrays with an explicit O(log(min(n, m))) requirement.
How you get there
1Partition both arrays so the combined left side holds exactly half the elements.
2The partition is correct when every left element is at most every right element.
3Binary search the cut position on the shorter array; the other cut follows arithmetically.
Solution
Python
def find_median_sorted_arrays(a: list[int], b: list[int]) -> float:
if len(a) > len(b):
a, b = b, a
n, m = len(a), len(b)
half = (n + m + 1) // 2
lo, hi = 0, n
while lo <= hi:
i = (lo + hi) // 2 # cut in a
j = half - i # cut in b follows
a_left = a[i - 1] if i > 0 else float("-inf")
a_right = a[i] if i < n else float("inf")
b_left = b[j - 1] if j > 0 else float("-inf")
b_right = b[j] if j < m else float("inf")
if a_left <= b_right and b_left <= a_right:
if (n + m) % 2:
return max(a_left, b_left)
return (max(a_left, b_left) + min(a_right, b_right)) / 2
if a_left > b_right:
hi = i - 1
else:
lo = i + 1
return 0.0
Time
O(log(min(n, m)))
Space
O(1)
What goes wrong
Forgetting the infinite sentinels at the array edges causes index errors on empty partitions.