Создание простого автозаполнения с использованием бинарного поиска - PullRequest
Новая
       5

Создание простого автозаполнения с использованием бинарного поиска

1 голос
/ 17 марта 2020

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

def binary_search(x,list):  
    l=0
    r=len(list)-1
    while l<=r:
        m=(r-1)/2+l
        m=int(m)
        if list[m][0][0:len(x)]==x:
            return list[m]
        elif list[m][0][0:len(x)]<x:
            l=m+1
        elif list[m][0][0:len(x)]>x:
            r=m-1
    return -1

И затем я добавляю список кортежей, которые я хочу, в новый список 

new_list=[]
s=input()
lexicographic_sort(list) #function that sorts using lambda
a=binary_search(s,list)
while a!=-1:
    new_list.append(a)
    list.remove(a)
    a=binary_search(s,list)

print(new_list)

Проблема заключается в том, что, когда я ввожу только 1 символ, я получаю результаты, которые хочу , но при вводе более 1 символа программа просто зависает. Более запутанная проблема при вводе более 1 символа состоит в том, что когда я удаляю, а l oop просто для вызова одного бинарного поиска, он возвращает мне кортеж, поэтому я не знаю, почему моя программа зависает.
Список [('school', 312), ('bus', 421), ('scheme', 53), ('and', 423), ('maybe', 143), ('schemes', 53), ('ands', 423), ('maybes', 143), ('schemess', 53), ('andsss', 423), ('maybesss', 143)] Вход 1: с c
Выход: [('schemess', 53), ('school', 312), ('scheme', 53), ('schemes', 53)]
Вход 2: может
Выход: (заморозить)

Ответы [ 3 ]

0 голосов
/ 17 марта 2020

Элемент "скользящая середина" должен быть рассчитан m=(r-l)/2+l, но у вас есть m=(r-1)/2+l.

Он должен быть: 

def binary_search(x,list):  
    l=0
    r=len(list)-1
    while l<=r:
        m=(r-l)/2+l
        m=int(m)
        if list[m][0][0:len(x)]==x:
            return list[m]
        elif list[m][0][0:len(x)]<x:
            l=m+1
        elif list[m][0][0:len(x)]>x:
            r=m-1
    return -1

Ссылка: python двоичный поиск

0 голосов
/ 17 марта 2020

встроенная сортировка будет сортировать это правильно ... нет необходимости в lamda 

terms = sorted(terms)

есть встроенный двоичный поиск отсортированных списков ... 

import bisect
idx = bisect.bisect(ordered_list_to_search,term)
print("Found: ",idx)

, чтобы вы могли скажем (так как похоже, что все численные значения c больше или равны 1) 

idx = bisect.bisect_right(terms,(search_term,0))
if idx < len(terms):
    print(terms[idx])
print("Nothing found...")
0 голосов
/ 17 марта 2020

В бинарном поиске основным шагом является поиск среднего элемента, как описано в https://en.wikipedia.org/wiki/Binary_search_algorithm (среди других мест) 

m = (r+l) // 2

У вас есть 

m=(r-1)/2+l

Например, середина 9 и 11 будет 10/2 + 9 = 14. Это неправильно. Это может привести к тому, что вы посмотрите на индексы, которые слишком велики для массива, и, таким образом, выйдете из программы с IndexError.

Вы захотите использовать //, чтобы гарантировать целочисленный результат. В этом случае желательно округление вниз.

Правда, должно быть ясно, что вы получаете исключение IndexError. Понятия не имею, что с этим якобы замерзает. Эта часть не имеет смысла.

...