Оглавление

Написать эту заметку меня побудили три обстоятельства.

Давайте же решим эту жуткую задачу.

Формулировка задачи дискретной бисекции

Любопытно, что когда задачу бисекции задают на собеседованиях, её редко формулируют исчерпывающе: что именно мы ищем, если искомых элементов нет? если их, наоборот, много? если искомый ключ выпадает за пределы массива?.. Давайте чётко оговорим, что мы ищем.

Дан сортированный массив a и ключ k. Следует найти такой индекс i, чтобы при вставке ключа k в a на позицию i, отсортированность массива a сохранялась. Если значения k в массиве уже имеются, то вставлять надо справа от них.

Из этого условия сразу понятно, что делать если k меньше всех элементов. Ответом должен быть 0. И что делать, если k больше всех элементов. Тут ответ должен быть len(a).

Естественно, все приведённые ниже выкладки можно проделать и для других условий (скажем, для вставки слева). Это не столь принципиально.

Использование инварианта

При написании таких алгоритмов, очень помогает понятие инварианта. Кстати, оно поможет вам убедить в своей правоте недалёкого оппонента.

Введём индексы l и r. Договоримся, что они всегда будут отвечать следующим условиям:

Для всех i < l: a[i] <= k
Для всех i > r: a[i] >  k

Это и есть инвариант. (Обратите внимание на строгость/нестрогость неравенств. Здесь и далее это очень существенно.)

Начальные условия будут гарантировать выполнение инварианта:

l = 0          # индекс первого элемента
r = len(a) - 1 # индекс последнего элемента

То есть нет ни одного элемента с i < l или i > r. Это гарантирует, что инвариант не нарушается.

Условие завершения поиска:

r < l

То есть, все элементы рассмотрены. Любой индекс удовлетворяет одному из условий: i < l, i > r.

Ответом будет индекс l.

Это становится очевидным, если посмотреть на наш инвариант и условие выхода. Ясно, что после всех итераций у нас будет выполняться условие:

Для всех i <  l: a[i] <= k
Для всех i >= l: a[i] >  k

То есть l — это индекс первого элемента, который строго больше k.

Именно в это место надо вставить k по условию задачи.

Реализация дискретного метода деления отрезка пополам

Реализация проста:

def bis(a, k):
    l = 0
    r = len(a) - 1
    while r >= l:
        m = (r + l) // 2
        if a[m] <= k:
            l = m + 1
        else:
            r = m - 1
    return l

Строго говоря, «m=(r+l)//2» лучше писть как «m=r-(r-l)//2»; чтобы не было риска выйти за пределы int. Но для Python это не актуально.

И, заметьте, она корректно решает поставленную задачу и на пустом массиве и в других пограничных случаях. Это следует из того, что алгоритм никогда не нарушает инвариант и завершается в правильный момент.

Несмотря на то, что тут есть операций с индексами, которые могут показаться опасными, алгоритм работает правильно. Без каких-либо дополнительных проверок. Он не зацикливается, не выходит за пределы массива (за исключением случая, когда k больше всех элементов a, но это оговорено в условии).

Не верите? Посмотрите на него внимательно. А если есть сомнения, давайте его погоняем.

Иллюстрация работы метода деления отрезка пополам

Вот код, с помощью которого я гонял алгоритм:

#!/usr/bin/python2
# coding: utf8

'''
Метод деленеия пополам
Будем искать правую границу
лемма:
  a[i] <= k для всех i < L
  a[i] >  k для всех i > R
в начале
  L = 0
  R = len(a) - 1 # индекс последнего элемента
в конце
  R < L # т.е. рассмотрены все элементы
ответ в L
'''

from collections import defaultdict

def pr(a, l, r, m=None):
    markers = defaultdict(list)
    for k in 'lrm':
        if locals()[k] is not None:
            markers[locals()[k]].append(k.upper())
    print ''.join(
        map(lambda x: '\033[1;32m%3s\033[0m' % ''.join(markers.get(x, [])),
        range(-1, len(a) + 1))
    )
    print '  _ ' + ' '.join(map(lambda x: '%2d' % x, a)) + '  _'

def bis(a, k):
    l = 0
    r = len(a) - 1
    pr(a, l, r)
    while r >= l:
        m = (r + l) // 2
        pr(a, l, r, m)
        if a[m] <= k:
            l = m + 1
        else:
            r = m - 1
        pr(a, l, r)
    return l

for a, k in (
        ((1, 2, 3, 3, 4, 5, 6, 8, 9), 3),
        ((1, 2, 3, 3, 4, 5, 6, 8, 9), 7),
        ((1, 2, 3, 3, 4, 5, 6, 8, 9), 1),
        ((1, 2, 3, 3, 4, 5, 6, 8, 9), 0),
        ((1, 2, 3, 3, 4, 5, 6, 8, 9), 10),
        ((1,), 3),
        ((1,), 0),
    ):
    print "==========="
    print "k = %d" % k
    i = bis(a, k)
    print "result = %d" % i
    # вы можете также убедиться, что вставка
    # даёт абсолютно правильный результат
    #a = list(a)
    #a.insert(i, k)
    #print repr(a)

А вот результат:

===========
k = 3
     L                       R   
  _  1  2  3  3  4  5  6  8  9  _
     L           M           R   
  _  1  2  3  3  4  5  6  8  9  _
     L        R                  
  _  1  2  3  3  4  5  6  8  9  _
     L  M     R                  
  _  1  2  3  3  4  5  6  8  9  _
           L  R                  
  _  1  2  3  3  4  5  6  8  9  _
          LM  R                  
  _  1  2  3  3  4  5  6  8  9  _
             LR                  
  _  1  2  3  3  4  5  6  8  9  _
            LRM                  
  _  1  2  3  3  4  5  6  8  9  _
              R  L               
  _  1  2  3  3  4  5  6  8  9  _
result = 4
===========
k = 7
     L                       R   
  _  1  2  3  3  4  5  6  8  9  _
     L           M           R   
  _  1  2  3  3  4  5  6  8  9  _
                    L        R   
  _  1  2  3  3  4  5  6  8  9  _
                    L  M     R   
  _  1  2  3  3  4  5  6  8  9  _
                          L  R   
  _  1  2  3  3  4  5  6  8  9  _
                         LM  R   
  _  1  2  3  3  4  5  6  8  9  _
                       R  L      
  _  1  2  3  3  4  5  6  8  9  _
result = 7
===========
k = 1
     L                       R   
  _  1  2  3  3  4  5  6  8  9  _
     L           M           R   
  _  1  2  3  3  4  5  6  8  9  _
     L        R                  
  _  1  2  3  3  4  5  6  8  9  _
     L  M     R                  
  _  1  2  3  3  4  5  6  8  9  _
    LR                           
  _  1  2  3  3  4  5  6  8  9  _
   LRM                           
  _  1  2  3  3  4  5  6  8  9  _
     R  L                        
  _  1  2  3  3  4  5  6  8  9  _
result = 1
===========
k = 0
     L                       R   
  _  1  2  3  3  4  5  6  8  9  _
     L           M           R   
  _  1  2  3  3  4  5  6  8  9  _
     L        R                  
  _  1  2  3  3  4  5  6  8  9  _
     L  M     R                  
  _  1  2  3  3  4  5  6  8  9  _
    LR                           
  _  1  2  3  3  4  5  6  8  9  _
   LRM                           
  _  1  2  3  3  4  5  6  8  9  _
  R  L                           
  _  1  2  3  3  4  5  6  8  9  _
result = 0
===========
k = 10
     L                       R   
  _  1  2  3  3  4  5  6  8  9  _
     L           M           R   
  _  1  2  3  3  4  5  6  8  9  _
                    L        R   
  _  1  2  3  3  4  5  6  8  9  _
                    L  M     R   
  _  1  2  3  3  4  5  6  8  9  _
                          L  R   
  _  1  2  3  3  4  5  6  8  9  _
                         LM  R   
  _  1  2  3  3  4  5  6  8  9  _
                            LR   
  _  1  2  3  3  4  5  6  8  9  _
                           LRM   
  _  1  2  3  3  4  5  6  8  9  _
                             R  L
  _  1  2  3  3  4  5  6  8  9  _
result = 9
===========
k = 3
    LR   
  _  1  _
   LRM   
  _  1  _
     R  L
  _  1  _
result = 1
===========
k = 0
    LR   
  _  1  _
   LRM   
  _  1  _
  R  L   
  _  1  _
result = 0

Но надо ли реализовывать бисекцию?

Никогда не пишите бисекцию самостоятельно. Она уже есть во всех языках в стандартных библиотеках. В Python — это модуль bisect, в STL — std::binary_search и вариации.