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

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

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

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

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

# 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 в d" занял 0,4 секунды.

Самый простой должен использовать , делят пополам и перепроверяют одно положение, чтобы видеть, там ли объект:

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

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

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

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

принимая во внимание, что с set() , Вы подвергаетесь

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

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

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