Searching a combined 2 sorted array

Can an algorithm search a combined 2 sorted array in O( log(n) ) ??

Combined 2 sorted array:

Is a combination of 2 sorted arrays..

Example: {1,2,3,4,5} + {2,3,4,5,6,7,} = {1,2,3,4,5,2,3,4,5,6,7}

Unfortunately, you do not know the boundary of them

*Please note I know a solution that gives O( log(n) ) in amortized time, but I need that O( log(n) ) in only one search..

Edit:开发者_StackOverflow You can assume distinct elements

Thanks

I think in the worst case you have to examine each element of the combined array, which gives O(n) worst-case complexity.

Here is the intuition: Let's say you've examined some subset of elements and have found them to be monotonically increasing with their position, and that the element you're looking for isn't present in the subset. There's absolutely nothing you can do to discard part of the search space, since the element -- regardless of its magnitude -- can still be validly located at any unexamined position. In the worst case this condition can remain true until you have examined the entire array.

No you can't.

Proof:

Take any sorted array. Change any one of the elements into an arbitrary, new value X. The result is now either a sorted array or a combined 2-sorted array. You have to search for X. Because X was inserted in a random location without any reference to the contents of the rest of the array, the only way to find X is by brute force.