Как искать в бесконечном списке слов в отсортированном порядке для индекса, соответствующего слову в качестве ввода

Question

Меня смущает трудная проблема, с которой я сталкиваюсь с данным потоком, с которым я имею дело, чтобы улучшить линейное время O(n) ..

Поиск бесконечного списка слов в отсортированном порядке для индекса в соответствии со словом в качестве входных данных

с учетом бесконечного списка ["apple", "banana", "cat", "dog", ...] у нас есть класс A, где A.get(2) # => "cat" напишет функцию, возвращающую индекс для слова, заданного в качестве ввода для функции, следующим образом:

A.get_index("cat") # => 2

вы можете использовать A.get (), но не python .index () для последовательностей

Answer 1

IIU C, вы можете сделать это в O(log n) с модификацией бинарного поиска.

import bisect


def find(endless_haystack, needle):

    if endless_haystack[0] == needle:
        return 0

    i = 1
    hay = endless_haystack[i]
    while hay < needle:  # this is O(log n) where n is the index of the element
        i = 2 * i
        hay = endless_haystack[i]

    # from the loop before the element is between i and i // 2
    return bisect.bisect_left(endless_haystack, needle, i // 2, i)

Имейте в виду, что приведенный выше код представляет собой набросок фактического решения, вам необходимо проверить некоторые крайние случаи.

Answer 2

Просто перебирайте список, увеличивая счетчик до тех пор, пока не достигнете соответствующего значения

class A:
   [...]


   def get_index(self, item):
       i = 0
       while self.get(i) != item:
           i += 1
       return i

Примечание. Это не очень безопасный код. Но поскольку мы предполагаем, что список бесконечен, вы не рискуете выйти из индекса. Хотя существует риск переполнения ...

Answer 3

вы можете использовать встроенную функцию enumerate, которая дает вам индекс, и элемент:

def get_index(word, my_infinite_list):
    return next(i for i, e in enumerate(my_infinite_list) if e == word)

встроенная функция next будет проверять ваш список до тех пор, пока Вы найдете нужное слово