Dual Sorted Median Probe Problem

Dual Sorted Median Probe Problem — ExecCode Hard DSA Practice

Solve the Dual Sorted Median Probe problem on ExecCode. Free online hard DSA practice in Searching & Sorting. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given two integer arrays a and b. Both arrays are already sorted in non-decreasing order. Together they form one combined sorted sequence of length m + n, where m is the length of a and n is the length of b. Find the median of that combined sequence: If m + n is odd, the median is the single middle value. If m + n is even, the median is the average of the two middle values. Return the median as a floating-point number. Whole numbers should still be returned as floats, for example 2.0. A split middle should look like 2.5. You are given: a — first sorted array of integers b — second sorted array of integers The arrays may have different lengths. Either array may contain a single element. Duplicate values are allowed. An O(log(min(m, n))) solution is expected. Merging the two arrays into a new list is correct but too slow for large inputs.

Examples

Input {'a': [1, 3], 'b': [2]}; Output 2.0. Input {'a': [1, 2], 'b': [3, 4]}; Output 2.5. Input {'a': [0, 0], 'b': [0, 0]}; Output 0.0

Constraints

1 <= len(a) + len(b) <= 2 * 10^5 Arrays may be of unequal length; one array may contain a single element Values fit in 32-bit signed integers

Practice Dual Sorted Median Probe free on ExecCode. Browse DSA problems, topic map, and placement guides.