Binary search (bisection) in Python

Существует ли библиотечная функция, которая выполняет двоичный поиск по списку / кортежу и возвращает позицию элемента, если он найден, и 'False' (-1, None и т.д.), если нет?

Я нашел функции bisect_left / right в модуле bisect , но они все равно возвращают позицию, даже если элемента нет в списке. Это прекрасно подходит для их предполагаемого использования, но я просто хочу знать, есть ли элемент в списке или нет (не хочу ничего вставлять).

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

Редактировать, чтобы уточнить, для чего мне это нужно: я знаю, что словарь был бы очень хорошо приспособлен для этого, но я стараюсь максимально снизить потребление памяти. Я предполагал использовать что-то вроде таблицы двустороннего поиска. У меня в таблице есть список значений, и мне нужно иметь возможность доступа к значениям на основе их индекса. А также я хочу иметь возможность находить индекс определенного значения или None, если значения нет в списке.

Использование словаря для этого было бы самым быстрым способом, но (приблизительно) удвоило бы требования к памяти.

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

bisect_left находит первую позицию, p в которую элемент может быть вставлен в заданном отсортированном диапазоне, сохраняя порядок сортировки. Это будет позиция x if x exists в диапазоне. Если p это конечная позиция, x не был найден. В противном случае мы можем проверить, есть ли тамx, чтобы узнать, был ли x найден.

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

Почему бы не взглянуть на код для bisect_left / right и адаптировать его к вашим целям.

вот так:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

This is a little off-topic (since Moe's answer seems complete to the OP's question), but it might be worth looking at the complexity for your whole procedure from end to end. If you're storing thing in a sorted lists (which is where a binary search would help), and then just checking for existence, you're incurring (worst-case, unless specified):

Sorted Lists

• O( n log n) to initially create the list (if it's unsorted data. O(n), if it's sorted )


• O( log n) lookups (this is the binary search part)


• O( n ) insert / delete (might be O(1) or O(log n) average case, depending on your pattern)

Whereas with a set(), you're incurring

• O (n) для создания


• O (1) поиск


• O(1) вставка / удаление

На самом деле отсортированный список дает вам "следующий", "предыдущий" и "диапазоны" (включая вставку или удаление диапазонов), которые равны O (1) или O (| range |) с заданным начальным индексом. Если вы не часто используете такого рода операции, то сохранение в виде наборов и сортировка для отображения в целом могут оказаться более выгодным решением. set() в python очень мало дополнительных накладных расходов.

Возможно, стоит упомянуть, что документы bisect теперь предоставляют примеры поиска: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Повышение ValueError вместо возврата -1 или None более по–питоновски - list.index() делает это, например. Но, конечно, вы можете адаптировать примеры к своим потребностям.)