Двоичный поиск для вставки значения в отсортированный список - PullRequest
Новая
       72

Двоичный поиск для вставки значения в отсортированный список

0 голосов
/ 18 июня 2020

Я пытаюсь вставить значения из списка B в список A.

Список A всегда сортируется в порядке убывания и может быть довольно большим (2x10 ^ 5).

Список B всегда сортируется в порядке возрастания, а также может иметь размер 2x10 ^ 5

. Я хочу вставить значения от B до A, сохраняя при этом порядок убывания. Я использовал бинарный поиск, чтобы найти позиции индекса, в которые нужно добавить значение.

Однако в этом одном тестовом примере у меня есть странная ошибка, которую я не могу исправить 

def binarySearch(arr, low, high, x):
    while low < high:
        mid = low + (high - low) // 2;
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            high = mid - 1
        else:
            low = mid + 1
    if low >= high:
        return(low)

for i in B:
    indexpos = binarySearch(A, 0, len(A)-1, i)
    if indexpos == 0:
        A = [i] + A
    else:
        A = A[:indexpos+1] + [i] + A[indexpos+1:]
    print(A)

Вот пример, который работает: 

A = [100,100,50,40,40,20,10]
B = [5,25,50,120]

Output: A = [120, 100, 100, 50, 50, 40, 40, 25, 20, 10, 5]

Я не могу понять, почему этот не работает: 

A = [100,90,90,80,75,60]
B = [50,65,77,90,102]

Output: A = [102, 100, 90, 90, 90, 80, 75, 77, 65, 60, 50]

Любая помощь будет очень принята

Ответы [ 2 ]

4 голосов
/ 18 июня 2020

Ваш while l oop должен продолжаться, а low <= high, а вы должны return high. Только так вы убедитесь, что возвращаемый индекс имеет значение, не превышающее x.

В основном коде у вас не должно быть особого случая для indexpos == 0

Итак: 

def binarySearch(arr, low, high, x):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            high = mid - 1
        else:
            low = mid + 1
    return high

for i in B:
    indexpos = binarySearch(A, 0, len(A)-1, i)
    A = A[:indexpos+1] + [i] + A[indexpos+1:]

print(A)

Обратите внимание, что, поскольку вы читаете все значения в A , каждый раз, когда вы выполняете присвоение A , преимущество двоичного поиска равно нулю: одно присвоение на A стоит O (n) , где n - это размер A , а первый двоичный поиск «только» стоит O (вход) . Таким образом, шея bottle является присвоением A. Временная сложность этого алгоритма составляет O (нм) , где n и m - размеры оба списка.

Вы должны просто выделить необходимое дополнительное пространство для A только один раз, а затем переместить элементы из A (начиная с последнего реального значения в A ) в конец теперь расширенного списка, сравнивая со значениями из B (начиная слева направо): поместите значение из A или B там, и пройдите по обоим спискам вот так.

Это сделает процесс O (n + m) .

Вот реализация этой идеи: 

m = len(A)
n = len(B)
k = m + n

# extend A only once
A.extend([0] * n)

# move values to the extended area
m -= 1
for b in B:
    k -= 1
    while m >= 0 and A[m] < b:
        A[k] = A[m]
        k -= 1
        m -= 1
    A[k] = b

print(A)
1 голос
/ 18 июня 2020

Чтобы улучшить свой код, посмотрите ответ trincot; но, как он также сказал, имейте в виду, что использование двоичного поиска для каждого элемента B, вероятно, не самый эффективный метод здесь.

trincot предоставляет лучший алгоритм, и если вам нужно больше решения pythoni c, вы можно посмотреть здесь: Объединение двух отсортированных списков в Python

...