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

Question

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

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

Я думал об использовании 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

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

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

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

Answer 4

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

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

Answer 5

Проще всего использовать 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

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's answer с использованием модуля 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

На моем компьютере " если n в l " заняло 37 секунд, в то время как " если n in d " заняло 0,4 секунды.

Answer 9

Это один из них:

• не рекурсивный (что делает его более экономия памяти чем большинство рекурсивных подходов)
• на самом деле работающий
• быстро с тех пор, как это работает без каких-либо ненужных если это и условия
• основано на математическом утверждении это этаж (низкий + высокий)/2 всегда меньше, чем высокий где низкий является нижним пределом и высокий это верхний предел.
• проверено: 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

Answer 11

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

Answer 12

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

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

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

Answer 13

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

< р>

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) < 2:
        return intList[lowValue] == intValue or intList[highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue)/2)
    if intList[middleValue] == intValue:
        return True
    if intList[middleValue] > intValue:
        return binary_search(intList, intValue, lowValue, middleValue - 1)
   return binary_search(intList, intValue, middleValue + 1, highValue)

Answer 14

Ознакомьтесь с примерами в Википедии 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

Answer 15

'''
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

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

Answer 16

• 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)
  

Answer 17

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

Answer 18

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

// 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))

Answer 19

Мне нужен был бинарный поиск в 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

Answer 20

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

Python пополам используется, чтобы указать, куда вставить новое значение / элемент поиска в отсортированный список. Приведенный ниже код, который использует 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