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

177

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

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

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

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

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

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

rslite
источник
1
Чего вы пытаетесь достичь? Если значения уникальны, рассмотрите возможность использования набора и «если значение в наборе: что-то».
Кирк Штраузер
Для чего это стоит, «-1» считается верным; «0» будет ложным.
Символ
3
Я упомянул -1, потому что функция, которая возвращает индекс искомого элемента в массиве, может уже вернуть 0, поэтому -1 возвращается, если элемент не найден (аналог поиска по подстроке).
rslite
3
Если вы используете NumPy, np.searchsortedэто полезно. docs.scipy.org/doc/numpy/reference/generated/…
Роман Шаповалов

Ответы:

238
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
Дейв Абрахамс
источник
10
@volcano Как и binsearch в целом.
cubuspl42
4
@TomSwirly не так просто, как у вас, но правильно и все еще улучшение:if hi is None: hi = len(a)
Марк Рэнсом
Как насчет нисходящего порядка?
Парикшит Чалк
2
Можете ли вы добавить некоторые объяснения вне кода? Стандарты здесь изменились.
SS Anne
54

Почему бы не взглянуть на код для 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
Моу
источник
29
Я изначально добавил +1, но теперь я пришел к выводу, что это не очень хорошая вещь. Если следовать этому ответу, это вызовет много дублирования кода, и, как мы все знаем, действительно просто выполнить бинарный поиск.
Abyx
1
не должно быть hi = mid - 1в elif?
Павел Прагак
7
@ Павел: это два эквивалентных варианта, в зависимости от того, является ли верхняя граница включающей или исключающей. Вы можете изменить hi = midна hi = mid-1и hi = len(a)к hi = len(a)-1и while lo < hi:к while lo <= hi, и это будет эквивалентно правильно
user102008
2
почему бы не сделать что-то вроде: def binary_search (a, x, lo = 0, hi = None): i = bisect (a, x, lo, hi) вернуть i, если a [i] == x иначе -1 извините за форматирование - не уверен, как это сделать правильно в комментарии arrea
Vitali
1
Вы должны использовать, bisect.bisect_left()а не это.
alastair
37

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

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

  • 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 (| range |), с учетом начального индекса. Если вы не используете такие операции часто, тогда лучше хранить в виде наборов и сортировать для отображения. set()в питоне очень мало дополнительных накладных расходов.

Грегг Линд
источник
7
Есть еще одна вещь, которую получает отсортированный список. O (n) упорядоченный обход. С набором, равным O (n log n), вам приходится копировать ссылки на данные в список.
Всезнающий
1
Правда достаточно! Спасибо, что расширили то, что я имел в виду под поиском по диапазону. Между прочим, полный обход - это тот же запрос диапазона между min, max, который равен O (k), где k = n :)
Грегг Линд
14

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

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

Петр Викторин
источник
11

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

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
Имран
источник
2
Хорошо, но код barfs, если вы не передаете значение 'hi'. Я бы написал это так: «def binary_search (a, x, lo = 0, hi = None): от деления на две части import bisect i = bisect (a, x, lo, hi или len (a)) return (i- 1, если a [i-1] == x else -1) "и проверить это следующим образом:" для i в диапазоне (1, 20): a = список (диапазон (i)) для aa в a: j = binary_search (a, aa) if j! = aa: напечатать i, aa, j "
hughdbrown
8

Это прямо из руководства:

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
arainchi
источник
6

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

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

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

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

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

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

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)
paulluap
источник
Это не чисто. Используйте scipy.optimizeдля этого.
Нил Г
4

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

# 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 секунды.

JRB
источник
2
Это не всегда хороший вариант по нескольким причинам: 1) дикты / наборы занимают больше памяти. 2) если у него не так много в списке, бинарный поиск может быть быстрее. 3) преобразование списка в dict является операцией O (n), в то время как двоичный поиск - O (log n).
Джейсон Бейкер
3
Что касается FYI, накладные расходы "set" в python по сравнению со списками python очень и очень низки. И они очень быстро для поиска. Где бинарный поиск действительно превосходен - это поиск диапазонов.
Грегг Линд
Преобразование списка может быть O (n), но сортировка данных в списке, что вам нужно сделать перед двоичным поиском, хуже. Откуда поступают данные, вы, вероятно, можете вставить их в словарь по ходу дела. Я согласен, что память может быть проблемой.
Марк Бейкер
4

Этот:

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

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
Матеуш Пиотровский
источник
Можете ли вы поделиться тестами?
спасательный круг
2

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

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i
Флоран
источник
2

Хотя в Python нет явного алгоритма двоичного поиска, существует модуль, bisectпредназначенный для поиска точки вставки элемента в отсортированном списке с помощью двоичного поиска. Это можно «обмануть» при выполнении бинарного поиска. Самым большим преимуществом этого является то же преимущество, которое имеет большинство библиотечного кода - он высокопроизводительный, хорошо протестированный и просто работает (в частности, бинарный поиск может быть довольно сложным для успешной реализации - особенно если крайние случаи не рассматриваются тщательно).

Основные типы

Для базовых типов, таких как Strings или Ints, это довольно просто - все, что вам нужно, это bisectмодуль и отсортированный список:

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

Вы также можете использовать это, чтобы найти дубликаты:

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

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

Объекты

Для пользовательских типов или объектов все немного сложнее: вы должны убедиться, что реализовали богатые методы сравнения, чтобы получить правильное сравнение.

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

Это должно работать как минимум в Python 2.7 -> 3.3

stephenfin
источник
1

Использование dict не приведет к удвоению использования вашей памяти, если только хранящиеся вами объекты не будут действительно крошечными, поскольку значения являются только указателями на реальные объекты:

>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True

В этом примере «foo» сохраняется только один раз. Это имеет значение для вас? И сколько конкретно предметов мы говорим?

Кирк Штраузер
источник
Речь идет о цифрах и о многих из них :) Я хотел бы использовать массив почти такой же большой, как память компьютера. Я знаю, что основа моей проблемы может быть неправильной, но мне было любопытно отсутствие метода двоичного поиска.
rslite
1
Вы не можете иметь ключевой объект, достаточно маленький, чтобы квалифицировать его как «действительно крошечный». Минимальная стоимость объекта - 3 слова (тип, refcount, полезная нагрузка), в то время как список добавляет 1 слово, набор добавляет 1 слово, а диктант добавляет 2 слова. Все три (list / set / dict) также каким-то образом предварительно распределяют пространство, что является еще одним множителем, но все же недостаточно для значения.
Rhamphoryncus
1

Этот код рекурсивно работает со списками целых чисел. Ищет простейший сценарий: длина списка меньше 2. Это означает, что ответ уже существует, и выполняется проверка для проверки правильности ответа. Если нет, то среднее значение устанавливается и проверяется на правильность, если не делится пополам, снова вызывая функцию, но устанавливая среднее значение в качестве верхнего или нижнего предела, сдвигая его влево или вправо.

def binary_search (intList, intValue, lowValue, highValue):
    if (highValue - lowValue) <2:
        вернуть intList [lowValue] == intValue или intList [highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue) / 2)
    if intList [middleValue] == intValue:
        верните True
    if intList [middleValue]> intValue:
        вернуть двоичный_поиск (intList, intValue, lowValue, middleValue - 1)
   вернуть двоичный_поиск (intList, intValue, middleValue + 1, highValue)
RCT
источник
1

Проверьте примеры в Википедии http://en.wikipedia.org/wiki/Binary_search_algorithm

def binary_search(a, key, imin=0, imax=None):
    if imax is None:
        # if max amount not set, get the total
        imax = len(a) - 1

    while imin <= imax:
        # calculate the midpoint
        mid = (imin + imax)//2
        midval = a[mid]

        # determine which subarray to search
        if midval < key:
            # change min index to search upper subarray
            imin = mid + 1
        elif midval > key:
            # change max index to search lower subarray
            imax = mid - 1
        else:
            # return index number 
            return mid
    raise ValueError
jdsantiagojr
источник
0
'''
Only used if set your position as global
'''
position #set global 

def bst(array,taget): # just pass the array and target
        global position
        low = 0
        high = len(array)
    while low <= high:
        mid = (lo+hi)//2
        if a[mid] == target:
            position = mid
            return -1
        elif a[mid] < target: 
            high = mid+1
        else:
            low = mid-1
    return -1

Я думаю, это намного лучше и эффективнее. поправьте меня пожалуйста :) Спасибо

iraycd
источник
0
  • s это список.
  • binary(s, 0, len(s) - 1, find) это начальный звонок.
  • Функция возвращает индекс запрашиваемого элемента. Если такого элемента нет, он возвращается -1.

    def binary(s,p,q,find):
        if find==s[(p+q)/2]:
            return (p+q)/2
        elif p==q-1 or p==q:
            if find==s[q]:
                return q
            else:
                return -1
        elif find < s[(p+q)/2]:
            return binary(s,p,(p+q)/2,find)
        elif find > s[(p+q)/2]:
            return binary(s,(p+q)/2+1,q,find)
AV94
источник
0
def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid
user3412550
источник
0

Бинарный поиск:

// List - values inside list
// searchItem - Item to search
// size - Size of list
// upperBound - higher index of list
// lowerBound - lower index of list
def binarySearch(list, searchItem, size, upperBound, lowerBound):
        print(list)
        print(upperBound)
        print(lowerBound)
        mid = ((upperBound + lowerBound)) // 2
        print(mid)
        if int(list[int(mid)]) == value:
               return "value exist"
        elif int(list[int(mid)]) < value:
             return searchItem(list, value, size, upperBound, mid + 1)
        elif int(list[int(mid)]) > value:
               return searchItem(list, value, size, mid - 1, lowerBound)

// Для вызова вышеуказанной функции используйте:

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1        
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))
jitsm555
источник
0

Мне нужен бинарный поиск в Python и общий для моделей Django. В моделях Django одна модель может иметь внешний ключ к другой модели, и я хотел выполнить некоторый поиск по найденным объектам моделей. Я написал следующую функцию, вы можете использовать это.

def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
    """
    This is a binary search function which search for given key in values.
    This is very generic since values and key can be of different type.
    If they are of different type then caller must specify `cmp` function to
    perform a comparison between key and values' item.
    :param values:  List of items in which key has to be search
    :param key: search key
    :param lo: start index to begin search
    :param hi: end index where search will be performed
    :param length: length of values
    :param cmp: a comparator function which can be used to compare key and values
    :return: -1 if key is not found else index
    """
    assert type(values[0]) == type(key) or cmp, "can't be compared"
    assert not (hi and length), "`hi`, `length` both can't be specified at the same time"

    lo = lo
    if not lo:
        lo = 0
    if hi:
        hi = hi
    elif length:
        hi = length - 1
    else:
        hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if not cmp:
            if values[mid] == key:
                return mid
            if values[mid] < key:
                lo = mid + 1
            else:
                hi = mid - 1
        else:
            val = cmp(values[mid], key)
            # 0 -> a == b
            # > 0 -> a > b
            # < 0 -> a < b
            if val == 0:
                return mid
            if val < 0:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
sonus21
источник
0

Выше было много хороших решений, но я не видел простого (KISS делает его простым (потому что я)) глупого использования встроенной функции Python / generic bisect для выполнения бинарного поиска. С небольшим количеством кода вокруг функции bisect, Я думаю, что у меня есть пример ниже, где я проверил все случаи для небольшого строкового массива имен.Некоторые из приведенных выше решений ссылаются на / говорят это, но, надеюсь, простой код ниже поможет любому запутаться, как я.

Python bisect используется, чтобы указать, куда вставить новое значение / элемент поиска в отсортированный список. Приведенный ниже код, который использует bisect_left, который будет возвращать индекс попадания, если найден элемент поиска в списке / массиве (обратите внимание, что bisect и bisect_right вернут индекс элемента после попадания или совпадения в качестве точки вставки) Если не найден , bisect_left вернет индекс к следующему элементу в отсортированном списке, который не = = значение поиска. Единственный другой случай - это когда элемент поиска будет находиться в конце списка, где возвращаемый индекс будет за концом списка / массива, и в коде ниже раннего выхода из Python с помощью «и» логических дескрипторов. (первое условие False Python не проверяет последующие условия)

#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
    search =input("Enter name to search for or 'none' to terminate program:")
    if search == "none":
        break
    i = bisect_left(names,search)
    print(i) # show index returned by Python bisect_left
    if i < (lenNames) and names[i] == search:
        print(names[i],"found") #return True - if function
    else:
        print(search,"not found") #return False – if function
##Exhaustive test cases:
##Enter name to search for or 'none' to terminate program:Zayed
##4
##Zayed found
##Enter name to search for or 'none' to terminate program:Zach
##3
##Zach found
##Enter name to search for or 'none' to terminate program:Jalan
##2
##Jalan found
##Enter name to search for or 'none' to terminate program:Donny
##1
##Donny found
##Enter name to search for or 'none' to terminate program:Adam
##0
##Adam found
##Enter name to search for or 'none' to terminate program:Abie
##0
##Abie not found
##Enter name to search for or 'none' to terminate program:Carla
##1
##Carla not found
##Enter name to search for or 'none' to terminate program:Ed
##2
##Ed not found
##Enter name to search for or 'none' to terminate program:Roger
##3
##Roger not found
##Enter name to search for or 'none' to terminate program:Zap
##4
##Zap not found
##Enter name to search for or 'none' to terminate program:Zyss
##5
##Zyss not found
боб
источник