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

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

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

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

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

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

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

17.10.2008 14:23:17
Что вы пытаетесь достичь? Если значения уникальны, рассмотрите возможность использования набора и «если значение в наборе: что-то».
Kirk Strauser 17.10.2008 15:03:45
Для чего это стоит, «-1» считается верным; «0» будет ложным.
Glyph 18.10.2008 05:12:54
Я упомянул -1, потому что функция, которая возвращает индекс искомого элемента в массиве, может уже вернуть 0, поэтому -1 возвращается, если элемент не найден (аналог поиска по подстроке).
rslite 18.10.2008 11:00:52
Если вы используете NumPy, np.searchsortedэто полезно. docs.scipy.org/doc/numpy/reference/generated/…
Roman Shapovalov 25.04.2013 11:56:09
20 ОТВЕТОВ
РЕШЕНИЕ
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
234
8.12.2019 14:51:36
@volcano Как и binsearch в целом.
cubuspl42 5.07.2014 20:13:18
@TomSwirly не так просто, как у вас, но правильно и все еще улучшение:if hi is None: hi = len(a)
Mark Ransom 21.10.2014 19:34:50
Как насчет нисходящего порядка?
Parikshit Chalke 7.06.2019 03:06:32
Можете ли вы добавить некоторые объяснения вне кода? Стандарты здесь изменились.
S.S. Anne 22.09.2019 18:31:18

Почему бы не посмотреть на код для 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
53
14.05.2012 06:29:13
Я изначально +1 добавил это, но теперь я пришел к выводу, что это не очень хорошая вещь. Если следовать этому ответу, это вызовет много дублирования кода, и, как мы все знаем, действительно просто выполнить бинарный поиск.
abyx 30.10.2009 16:23:15
не должно быть hi = mid - 1в elif?
Paweł Prażak 5.02.2011 18:50:08
@ Павел: это два эквивалентных варианта, в зависимости от того, является ли верхняя граница включающей или исключающей. Вы можете изменить hi = midна hi = mid-1и hi = len(a)к hi = len(a)-1и while lo < hi:к while lo <= hi, и это будет эквивалентно правильно
user102008 6.04.2011 10:42:37
почему бы не сделать что-то вроде: def binary_search (a, x, lo = 0, hi = None): i = bisect (a, x, lo, hi) вернуть i, если a [i] == x иначе -1 извините за форматирование - не уверен, как это сделать правильно в комментарии arrea
Vitali 29.02.2012 01:44:44
Вы должны использовать, bisect.bisect_left()а не это.
alastair 7.11.2012 11:26:12

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

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

4
17.10.2008 15:03:30
Это не всегда хороший вариант по нескольким причинам: 1) дикты / наборы занимают больше памяти. 2) если он не имеет много в списке, бинарный поиск может быть быстрее. 3) преобразование списка в dict является операцией O (n), в то время как двоичный поиск - O (log n).
Jason Baker 17.10.2008 15:10:09
Что касается FYI, накладные расходы "set" в python по сравнению со списками python очень и очень низки. И они очень быстро для поиска. Где бинарный поиск действительно превосходен - это поиск диапазонов.
Gregg Lind 17.10.2008 16:43:52
Преобразование списка может быть O (n), но сортировка данных в списке, что вам нужно сделать перед двоичным поиском, хуже. Откуда поступают данные, вы, вероятно, можете вставить их в словарь по ходу дела. Я согласен, что память может быть проблемой.
Mark Baker 20.10.2008 15:56:24

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

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

  • 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()в питоне очень мало дополнительных накладных расходов.

37
3.04.2012 14:41:13
Есть еще одна вещь, которую получает отсортированный список. O (n) упорядоченный обход. С набором, равным O (n log n), вам приходится копировать ссылки на данные в список.
Omnifarious 30.03.2010 19:47:58
Правда достаточно! Спасибо, что расширили то, что я имел в виду под поиском по диапазону Между прочим, полный обход - это тот же запрос диапазона между min, max, который равен O (k), где k = n :)
Gregg Lind 31.03.2010 12:35:54

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

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

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

1
17.10.2008 21:01:17
Речь идет о цифрах и о многих из них :) Я бы хотел использовать массив почти такой же большой, как память компьютера. Я знаю, что основа моей проблемы может быть неправильной, но мне было любопытно отсутствие метода двоичного поиска.
rslite 18.10.2008 11:07:54
Вы не можете иметь ключевой объект, достаточно маленький, чтобы квалифицировать его как «действительно крошечный». Минимальная стоимость объекта - 3 слова (тип, пересчет, полезная нагрузка), в то время как список добавляет 1 слово, набор добавляет 1 слово, а диктант добавляет 2 слова. Все три (list / set / dict) также каким-то образом предварительно распределяют пространство, что является еще одним множителем, но все же недостаточно для значения.
Rhamphoryncus 9.11.2009 20:37:08

Проще всего использовать 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
11
30.06.2010 03:01:31
Хорошо, но код 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 6.08.2009 20:02:05

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

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

13
23.04.2011 08:36:45

Этот код рекурсивно работает с целочисленными списками. Ищет простейший сценарий: длина списка меньше 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)
1
30.04.2012 21:49:00
'''
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

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

0
11.05.2012 17:02:27

Проверьте примеры в Википедии 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
1
10.10.2013 00:02:51

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

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

Я согласен, что ответ @ 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)
6
23.05.2017 11:54:43
Это не чисто. Используйте scipy.optimizeдля этого.
Neil G 30.10.2015 09:51:10

Хотя в 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

2
15.11.2013 18:03:48

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

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
7
29.12.2013 17:20:44
  • 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)
0
12.01.2016 00:05:04

Этот:

  • не рекурсивный (что делает его более эффективным с точки зрения памяти, чем большинство рекурсивных подходов)
  • на самом деле работает
  • быстро , так как она работает без каких - либо ненужных если х и условий
  • основанный на математическом утверждении, что нижний предел (низкий + высокий) / 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
4
13.04.2020 14:12:35
Можете ли вы поделиться тестами?
lifebalance 6.08.2017 03:28:28

Мне нужен бинарный поиск в 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
0
12.07.2017 16:26:14
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
0
18.05.2017 00:41:57

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

// 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))
0
26.06.2017 13:43:58

Выше было много хороших решений, но я не видел простого (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
0
18.04.2018 19:15:07