Двоичный поиск в 2 отсортированных целочисленных массивах

Question

Существует большой массив, состоящий из 2 небольших целых массивов, написанных один в конце другого. Оба небольших массива сортируются по возрастанию. Нам нужно как можно быстрее найти элемент в большом массиве. Моя идея заключалась в том, чтобы найти конец левого массива binsearch в большом массиве, а затем реализовать 2 биншеры на небольших массивах. Проблема в том, что я не знаю, как найти эту цель. Если у вас есть идея, как найти элемент, не найдя границ меньших массивов, пожалуйста!

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

1. 1 2 3 4 5 6 7 (все элементы второго массива больше, чем максимум первого массива)

2. 100 1 (оба массива имеют только один элемент)

3. 1 3 5 2 4 6 или 2 4 6 1 3 5 (наиболее распространенные ситуации)

Answer 1

Эта проблема не может быть решена в гарантированной временной сложностью быстрее, чем O (n) и вообще не может быть решена для определенных массивов. Бинарный поиск выполняется в O (log n) для отсортированного массива, но большой массив не может быть отсортирован и в худшем случае потребует одного или нескольких сравнений на элемент, что является O (n). Лучшая гарантированная временная сложность - O (n) с тривиальным алгоритмом: сравнивайте каждый элемент со своим соседом, пока не найдете «точку поворота» с A[i] > A[i+1]. Однако, если вы используете поиск по ширине, вам может повезти и найти «поворотную точку» на ранней стадии.

Доказательство того, что проблема неразрешима для некоторых массивов: пусть массив M = [A B] будет нашим большим массивом. Чтобы найти точку, где встречаются массивы, мы ищем индекс i, где M[i] > M[i+1]. Теперь позвольте A=[1 2 3] и B=[4 5]. В массиве M нет индекса, для которого выполняется условие, поэтому проблема не разрешима для некоторых массивов.

Неофициальное доказательство для первых: пусть M=[A B] и A=[1..x] и B=[(x+1)..y] - это два отсортированных массива. Затем поменяйте местами позиции x и y в M. У нас нет способа найти индекс x без (в худшем случае) проверки каждого индекса, таким образом, проблема O (n).

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

(С практической точки зрения, вы никогда не должны делать это в программе. Два массива должны быть разделены. Если это невозможно, добавьте длину любого массива в большом массиве.)

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

Start with the interval [0..n-1] where n is the length of the big array. 
Make a list of intervals and put the starting interval in it. 
For each interval in the list: 
    if the interval is only two elements and the first element is greater than the last 
     we found the turning point, return it 
    else if the interval is two elements or less 
     remove it from the list 
    else if the first element of the interval is greater than the last 
     turning point is in this interval 
     clear the list 
     split this interval in two equal parts and add them to the list 
    else 
     split this interval in two equal parts and replace this interval in the list with the two parts 

Я думаю, что в ширину первый подход увеличит шансы найти интервал, где A[first] > A[last] рано. Обратите внимание, что этот подход не будет работать, если точка поворота находится между двумя интервалами, но вам нужно начать. Я бы сам это испытал, но, к сожалению, сейчас у меня нет времени.