почему бы не посмотреть на код для 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

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

Сортировка Списков

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

а с set(), вы производите

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

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

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

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

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

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

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

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

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

С docsbisect.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)

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

# 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 в л" потребовалось 37 секунд, в то время как "если N В D" занял 0,4 секунды.

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

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

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

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

для основных типов, таких как строки или 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

Это:

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

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

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

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

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

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) &lt 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)

Проверьте примеры в Википедии 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

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

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

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

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

Бинарного Поиска :

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

Мне нужен двоичный поиск в python и generic для моделей 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

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