Бинарный поиск (бисекция) в Python

Question

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

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

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

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

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

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

Answer 1

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to 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

Answer 2

Почему бы не взглянуть на код для 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

Answer 3

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

Сортированные списки

• O (n log n) для первоначального создания списка (если это несортированные данные. O (n), если они отсортированы)
• O (log n) поисков (это часть двоичного поиска)
• O (n) вставить / удалить (может быть в среднем O (1) или O (log n), в зависимости от вашего шаблона)

Принимая во внимание, что с set() вы получаете

• O (n) для создания
• O (1) поиск
• O (1) вставить / удалить

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

Answer 4

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

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

Answer 5

Самое простое - использовать пополам и проверить одну позицию назад, чтобы увидеть, есть ли там элемент:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

Answer 6

Это правильно из руководства:

http://docs.python.org/2/library/bisect.html

8.5.1. Поиск отсортированных списков

Вышеуказанные функции bisect () полезны для поиска точек вставки, но их сложно или неудобно использовать для обычных задач поиска. Следующие пять функций показывают, как преобразовать их в стандартный поиск для отсортированных списков:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Так что с небольшой модификацией ваш код должен быть:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

Answer 7

Я согласен, что @ ответ DaveAbrahams с использованием модуля bisect является правильным подходом. В своем ответе он не упомянул одну важную деталь.

Из документов bisect.bisect_left(a, x, lo=0, hi=len(a))

Модуль бисекции не требует предварительного вычисления массива поиска. Вы можете просто представить конечные точки для bisect.bisect_left вместо него, используя значения по умолчанию 0 и len(a).

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

Просто предоставьте объект, который определяет __getitem__ как a

Например, мы могли бы использовать алгоритм деления пополам, чтобы найти квадратный корень с произвольной точностью!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

Answer 8

Если вы просто хотите увидеть, присутствует ли он, попробуйте превратить список в диктовку:

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

На моей машине «if n in l» заняло 37 секунд, а «if n in d» - 0,4 секунды.

Answer 9

Это:

• не рекурсивно (что делает его более эффективным для памяти , чем большинство рекурсивных подходов)
• на самом деле работает
• быстро, так как он работает без каких-либо ненужных if's и условий
• на основе математического утверждения , что пол (низкий + высокий) / 2 всегда меньше высокий , где низкий нижний предел и high верхний предел.
• проверено: D

---

def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

Answer 10

Решение Дейва Абрахамса это хорошо. Хотя я бы сделал это минималистично:

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i