Finding a match in two collections Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a &lt; b = card(B)$. Both collections are sorted in ascending order. There is at least one item ${x}$ which is contained both in $A$ and $B$. 

Question: what is the fastest algorithm to find the smallest $x$ and what is its $T(n)$ in Big O notation?    

Note: card() means the size of array (say: card(A) = 10 means a declaration in C/C++ would be int[10] A with indices 0...9). 

Note 2: as I am new to CS.SE and learn CS as enthusiast, so far I have not been exposed to any fancy algorithm to solve this. My initial (naive) guess would be brute-search approach, but this is obviously not efficient for large $A$ and $B$. Your thoughts and pieces of advice would be then highly appreciated. 

The priority is practical efficiency, so something around polynomial time-algorithm would be nice. Note, that the number of elements in both collections will be very substantial (above 10^30).
Some ideas for a special case.

If all the elements have a limited range N (all the elements in A and B are bigger than zero and smaller than N), then you can accomplish this task by O(N*log(|A| + |B|)) as following:

for i &lt;- 0, 1, ..., N:
    binary search in A to see whether i is in A
    binary search in A to see whether i is in B
    if i is both in A and B then
        x &lt;- i
        break


This solution will be practically efficient if the N is not so big (for example 10^7) then it will solve the problem even when |A| and |B| are as large as 10^30 (though it is not practical to store them in any place).

The calculation: $N*\log{(|A| + |B|)} = 10^7 * \log{(2*10^{30})} \approx 3*10^8$

Besides, I do not think you can find a practically efficient algorithm for general case for card(A) and card(B) as much as 10^30. The general algorithm, in my opinion, is at least O(|A|+|B|) as following:

ia &lt;- 0
ib &lt;- 0
while A[ia] != B[ib] do
    if A[ia] &gt; B[ib] then
        ib &lt;- ib + 1
    else
        ia &lt;- ia + 1
x &lt;- A[ia]