Finding optimal separating value

Question

Problem description

We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd number to predict which set an element belongs to. If an element is smaller than X, it will be assigned to A,and if it is bigger - to B. The value should be optimal, meaning the number of improperly matched values should be minimal. For example, if A = [2,4,6] and B = [6, 10, 12]. Separating value 3 would cause 2 mismatched values 4 and 6. Optimal would be 5 or 7, both causing one improper matched element. The algorithm is supposed to return an optimal separating value (only one of there are many) and the number of mismatched items.

My ideas

At first I thought about using Binary Search for each element of A to find a number of elements of B smaller than it. Then repeat for B.

A better idea would be to generate candidates for such separating numbers. For example, if we only have values 10, 50, 100 we don't have to check all odd numbers, we can just check 9, 11, 51, 101. We could then calculate prefix sums, indicating how many numbers from A are bigger than the checked value and how many elements from B are smart than that value. The sum of the two sums for a number would be the total number of errors. The only thing left is to find the value with minimal errors.

Is this approach even near optimal, maybe we can find a better way. Also, calculating such prefix sums can be tricky because if we want not to care about the range of numbers we would have to find a way to skip some numbers and that makes our iteration harder, although possible.

What are your ideas? Some pseudocode or code in Python is very welcome.

Answer 1

Initialize an array of pairs $T[i] = (x, c)$ containing all elements of $A$ and $B$. Let $x$ be the elements themselves, and $c = 0$ if the element came from $A$ and $c = 1$ if the element came from $B$. Then sort $T$ based on the $x$ values in ascending order.

Then the number of mistakes you'd get if you choose a value between $T[i]\text{.}x$ and $T[i+1]\text{.}x$ is:

$$\sum_{j=0}^i T[j]\text{.}c + \sum_{j=i+1}^n\left(1 - T[j]\text{.}c\right) = $$ $$(n - i) +\sum_{j=0}^i T[j]\text{.}c - \sum_{j=i+1}^nT[j]\text{.}c = $$ $$(n - i) +2\sum_{j=0}^i T[j]\text{.}c - \sum_{j=0}^nT[j]\text{.}c = $$ $$- i +2\sum_{j=0}^i T[j]\text{.}c - C$$

where $C$ is just a constant, which doesn't matter if you wish to minimize the quantity. So to find the optimal value:

S = 0
best = inf
best_i = 1
for 1 <= i <= n:
    S += 2*T[i].c
    if S - i < best:
        best = S - i
        best_i = i