Binary search in merged arrays.

Question

Given two arrays, sorted by ascending. Result array is first array and second at the end of first.

Example: [1, 4, 7, 11] and [2, 3, 5]. Result array is [1, 4, 7, 11, 2, 3, 5].

How to find element in this array in $O($log n)?

Answer 1

It does not seem possible. Imagine you are given the array $[1,2,3,...,i-1,2^n,i+1,...,n]$, i.e. an ordered array with just one very big number $2^n$ instead of $i$. This is of the form you are describing. If you look for $2^n$, the other elements give you no information, you have to look in every cell, so it has to take time $\Omega(n)$.