**Input:**2 sets of positive integers presented as arrays $A = [a_{1},a_{2},\ldots,a_{n}]$ & $B =[b_{1},b_{2},\ldots,b_{n}]$

**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 $=$.