Найти следующий нижний элемент в отсортированном списке

Question

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

Мой O (n) подход:

index=0
for i,value in enumerate(mylist):
    if value>compareValue:
        index=i-1

Существует ли тип данных для решения этой проблемы в O (log n)?

С наилучшими пожеланиями Себастьян

Answer 1

Как насчет пополам ?

>>> import bisect
>>> float_list = [1.0, 1.3, 2.3, 4.5]
>>> i = bisect.bisect_left(float_list, 2.5)
>>> index = i - 1
>>> index
2

Возможно, вам придется обрабатывать случай поиска значения, которое меньше или равно наименьшему / левому значению в списке отдельно (index == -1 в этом случае).

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

Answer 2

Вы можете выполнить двоичный поиск в массиве / списке, чтобы получить индекс искомого объекта и получить индекс под ним, чтобы получить нижнюю запись (учитывая, что на самом деле есть более низкая запись!). 1001 *

См .: Бинарный поиск (деление пополам) на Python

Будьте осторожны при сравнении чисел с плавающей запятой на равенство!

Answer 3

import bisect

def next_lower_value(values_list, input_value):
    index= bisect.bisect_left(values_list, input_value)
    if index == 0: # there's not a "next lower value"
        raise NotImplementedError # you must decide what to do here
    else:
        return values_list[index - 1]

>>> l= [11, 15, 23, 28, 45, 63, 94]
>>> next_lower_value(l, 64)
63
>>> next_lower_value(l, 63)
45
>>> next_lower_value(l, 1000)
94
>>> next_lower_value(l, 1)
Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    next_lower_value(l, 1)
  File "<pyshell#26>", line 4, in next_lower_value
    raise NotImplementedError # you must decide what to do here
NotImplementedError

Поскольку вы запрашиваете index , а не следующее более низкое значение, измените функцию next_lower_value, чтобы она возвращала index - 1 вместо values_list[index - 1].

Answer 4

Используйте модуль bisect . Функция

bisect.bisect_left(mylist, compareValue)

возвращает правильную точку вставки для элемента в списке для поддержания отсортированного порядка.

Answer 5

Если я читаю это право, следующий нижний элемент - это первый элемент в списке, который меньше или равен x. Документация bisect для поиска отсортированных списков дает эту функцию:

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

Answer 6

Чтобы ответить на часть вопроса о типах данных: в общем смысле, тип данных, наиболее подходящий для поиска вещей за время O (log n) (при сохранении производительности O (1) для вставок и удалений!), Представляет собой двоичное дерево.Вы можете найти что-то в этом, приняв ряд лево-правых решений, что очень похоже на то, как вы выполняете бинарный поиск в линейном списке, но (IMO) немного более концептуально интуитивно.Судя по тому, что я мало знаю о Python, двоичные деревья, похоже, не входят в стандартную библиотеку языка.Для вашего приложения, вероятно, было бы бесполезно включать реализацию только для этой цели.

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