Given two sets of integers find an integer in the first set furthest away from all members of the second set

If given two sets of integers how can I find an integer in the first set furthest away from all members of the second set. The distance of two integers is the absolute value of difference of the two integers. To clarify the question: if $$a_i$$ and $$b_j$$ are elements of the first and the second sets, I am trying to find $$i$$ such as $$\operatorname*{argmax}_{i} (\min_{j} |a_i - b_j|)$$

Thanks!

• What did you try? Commented Feb 19 at 13:36
• @Nathaniel I clarified the question. I tried bruteforce only. Commented Feb 19 at 15:11
• @hovnatan Thanks for clarifying the question, I've updated my answer Commented Feb 19 at 16:24
• what is a set? unordered list? sorted list? bitmap? generator function? Commented Feb 20 at 0:36

Assume your sets are $$A$$ and $$B$$, with $$|A|=n$$ and $$|B|=m$$. Let $$k=\max(n,m)$$. This is the procedure:
1. Join the two sets $$X=A\cup B$$ in $$\Theta(k)$$ time.
2. Sort $$X$$ in $$\Theta((n+m)\log(n+m))=\Theta(k\log k)$$ time.
3. Scan the sorted set and, each time you encounter an element of $$A$$, it is sufficient to compute its distance from the previous element of $$B$$ and the next element of $$B$$ and take the minimum of the two distances. In this process, keep track of the maximum of these minimum distances. This can be easily done in $$\Theta(k)$$.
So, the overall time complexity is $$\Theta(k\log k)$$.