Question: Is there a non-empty intersection?
Output: $[i, j]$ such that $a_{i} = b_{j}$ if it exist
We want the upper and lower bounds. Make them as tight as possible.
Upper Bound:
- Sort A in increasing order
- Sort B in increasing order
- "Merge" A & B
Check if $a_{1} = b_{n}$ or $a_{1} > b_{n}$ or $a_{1} < b_{n}$.
If $a_{1} = b_{n}$ then we are done.
If $a_{1} > b_{n}$ then proceed by checking if $a_{1} = b_{n-1}$ or $a_{1} > b_{n-1}$ or $a_{1} < b_{n-1}$.
If $a_{1} < b_{n}$ then proceed by checking if $a_{2} = b_{n}$ or $a_{1} > b_{n}$ or $a_{1} < b_{n}$.
Sorting takes $O(n\lg{n})$ steps. The "merging" part takes $2n-1$ steps on the worst case scenario. So the total number of steps to solve the problem is $$O(n\lg{n}) + O(n\lg{n}) + 2n-1$$ $$= O(n\lg{n})$$
Lower Bound:
Oracle decides on an ordering of the form:
$$a_{i_{1}} \le b_{j_{1}}\le a_{i_{2}}\le b_{j_{2}}\le\ldots\le b_{j_{n}}$$
Oracle answers $<$ or $>$ all questions consistently with the ordering above until the algorithm outputs an answer. If the algorithm answers NONE and one of these test is not made then Oracle says $=$.
