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.
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.