Поиск объединенного 2 отсортированного массива

Question

Может ли алгоритм искать объединенный 2 отсортированный массив в O (log (n)) ??

Объединенный 2 отсортированный массив :
Является ли комбинация из 2 отсортированных массивов ..
Пример: {1,2,3,4,5} + {2,3,4,5,6,7,} = {1,2,3,4,5,2,3,4,5,6,7}
К сожалению, вы не знаете их границы

* Обратите внимание, я знаю решение, которое дает O (log (n)) в амортизированном времени, но мне нужно, чтобы O (log (n)) только в одном поиске

Редактировать: Вы можете предполагать различные элементы

Спасибо

Answer 1

Нет, ты не можешь.

Доказательство:

Взять любой отсортированный массив. Измените любой из элементов на произвольное новое значение X. Результатом теперь является либо отсортированный массив, либо комбинированный 2-отсортированный массив. Вы должны искать X. Поскольку X был вставлен в произвольном месте без какой-либо ссылки на содержимое остальной части массива, единственный способ найти X - это перебор.

Answer 2

Я думаю, что в худшем случае вам нужно изучить каждый элемент объединенного массива, что дает O(n) сложность наихудшего случая.

Вот интуиция: допустим, вы изучили некоторое подмножествоэлементы и обнаружили, что они монотонно увеличиваются с их положением, и что элемент, который вы ищете, отсутствует в подмножестве.Вы абсолютно ничего не можете сделать, чтобы отбросить часть пространства поиска, поскольку элемент - независимо от его величины - все еще может быть корректно расположен в любой нерассмотренной позиции.В худшем случае это условие может оставаться верным, пока вы не изучите весь массив.