O (log n) алгоритм для нахождения элемента, имеющего ранг i, в объединении предварительно отсортированных списков

Question

Учитывая два отсортированных списка, каждый из которых содержит n действительных чисел, существует ли алгоритм времени O (log n) для вычисления элемента ранга i (где i выполняет поиск по индексу в возрастающем порядке) в объединении двух списков, предполагая, что элементы двух списков различны?

EDIT: @BEN: Это то, чем я занимаюсь, но до сих пор не понимаю.

У меня есть примеры;

Список А: 1, 3, 5, 7 Список Б: 2, 4, 6, 8

Найти ранг (i) = 4.

Первый шаг: i / 2 = 2; Список А теперь содержит А: 1, 3 Список B теперь содержит B: 2, 4

         compare A[i] to B[i] i.e 

                 A[i] is less;

                 So the lists now become :

                   A: 3 
                   B: 2,4

Второй шаг: I / 2 = 1

         List A now contains A:3
         List B now contains B:2 

         NoW I HAVE LOST THE VALUE 4 which is actually the result ...

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

Answer 1

Да

Вы знаете, что элемент находится внутри индекса [0,i] первого списка или [0,i] второго списка. Возьмите элемент i/2 из каждого списка и сравните. Продолжить путем деления пополам.

Я не включаю код, потому что эта проблема очень похожа на домашнюю работу.

РЕДАКТИРОВАТЬ: бисекция является методом бинарного поиска. Это работает так:

Предположим, я = 10; (индексирование на основе нуля, мы ищем 11-й элемент в целом).

На первом шаге вы знаете, что ответ либо в списке 1 (0 ... 10), либо в списке 2 (0 ... 10). Возьмите a = list1 (5) и b = list2 (5).

Если a> b, то в списке list1 есть 5 элементов, предшествующих a, и, по крайней мере, 6 элементов в list2, предшествующих a. Таким образом, a является верхней границей результата. Аналогично, в списке list2 есть 5 элементов, предшествующих b, и менее 6 элементов в list1, предшествующих b. Таким образом, b является нижней границей результата. Теперь мы знаем, что результат находится либо в list1 (0..5), либо в list2 (5..10). Если a Мы просто повторяем этот процесс, сокращая размер пространства поиска пополам на каждом шаге. Разделение пополам относится к тому факту, что мы выбираем средний элемент (биссектриса) из диапазона, который, как мы знаем, включает в себя результат.

Таким образом, единственное различие между этим и двоичным поиском состоит в том, что в двоичном поиске мы сравниваем со значением, которое ищем, но здесь мы сравниваем со значением из другого списка.

ПРИМЕЧАНИЕ: это на самом деле O(log i), что лучше (по крайней мере, не хуже), чем O(log n). Кроме того, для малых i (возможно, i <100) было бы на самом деле меньше операций по объединению первых элементов i (линейный поиск вместо деления пополам), потому что это намного проще. Когда вы добавляете в поведение кеша и локальность данных, линейный поиск может быть быстрее для меня до нескольких тысяч. </p>

Кроме того, если i> n, то полагаться на то, что результат должен быть ближе к концу любого списка, ваш начальный диапазон кандидатов в каждом списке от ((i-n) .. n)

Answer 2

Вот как вы это делаете.

Пусть первый список будет ListX, а второй список будет ListY.Нам нужно найти правильную комбинацию ListX[x] и ListY[y], где x + y = i.Поскольку x, y, i являются натуральными числами, мы можем немедленно ограничить нашу проблемную область до x*y.И используя уравнения max(x) = len(ListX) и max(y) = len(ListY), теперь у нас есть подмножество x*y элементов в форме [x, y], которые нам нужно найти.

Что вы будете делать, это упорядочивать эти элементы следующим образом[i - max(y), max(y)], [i - max(y) + 1, max(y) - 1], ..., [max(x), i - max(x)].Затем вы разделите этот список пополам, выбрав среднюю комбинацию [x, y].Поскольку списки упорядочены и различны, вы можете проверить ListX[x] < ListY[y].Если true, тогда мы делим пополам верхнюю половину наших [x, y] комбинаций, или если false, то мы делим пополам нижнюю половину.Вы будете продолжать делить пополам, пока не найдете правильную комбинацию.

Я оставил много деталей, но это основная суть.Это действительно O (log (n))!

Редактировать: Как Бен указал на это на самом деле O(log(i)).Если мы допустим n = len(ListX) + len(ListY), то мы знаем, что i <= n.

Answer 3

edit: упс, я неправильно понял вопрос. Я думал, учитывая значение, вы хотите найти ранг, а не наоборот. Если вы хотите найти значение по рангу, то вот как это сделать в O(log N):

Да, вы можете сделать это в O(log N), если список допускает O(1) произвольный доступ (т. Е. Это массив, а не связанный список).

• Двоичный поиск по L1
• Двоичный поиск по L2
• Сумма индексов

Вы должны решить математику, +1, -1, что делать, если элемент не найден и т. Д., Но это идея.

Answer 4

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

Вам не нужно сортировать, так как у вас есть два списка, которые уже отсортированы, и вы можете сохранить этот порядок как часть слияния.