binary search

_winnie — 30.04.2015 В книге "жемчужины программирования" сообщается, что невозможно написать binary search с первого раза.

На самом деле его невозможно написать с первого раза, если не осознаешь что такое инвариант цикла. Если осознаёшь - то скорее всего запросто напишешь (я вот уже в третий раз за год написал).

Если не осознаёшь инвариант цикла, то с большой вероятностью будет одна из ошибок:

* mid = (lo+hi)/2 или hi/2+lo/2 ? (и нет, дело не в overflow, эти формулы просто разные (1+3)/2 != 1/2 + 3/2 ).
* индексация за пределами массива (начинаем проверять элемент array[-1]).
* вечное зацикливание, когда на маленьком массиве середина посчитанная с ±1 ошибкой - совпадает с концом или началом массива (массив длины 2 остается массивом длины 2).
* неправильный выбор элемента для сравнения, array[mid] или array[mid-1]?
* неправильный выбор между < и <=
* отсутствие осознания, что найдётся, когда есть несколько элементов равных искомому, или ни одного

Как писать двоичный поиск чтобы он не бажил:
* Выбрать инвариант "если искомый элемент существует, то он в [lo, hi)", изначально выбрать lo,hi = 0, N.
* mid = lo+(hi-lo)/2 (при этом для кода верно утверждение "промежуток длиннее 1 всегда укоротится").
* Если ищем первый среди равных - то сравнение выглядит как key<=array[mid-1], если последний - key
* в зависимости от сравнения присваиваем mid в lo или hi (в любом случае, не mid-1).

---

Двоичный поиск для равномерно распределённых ключей (хешей) ускоряется простым хаком "для каждого из 65536 двубайтовых префиксов запомнить, где он начинается", это убирает 16 начальных итераций.
Вместо 16 можно выбрать что-то другое, исходя из количества RAM и размера массива. Если не жалко оперативной памяти, а элементы совсем рандомные (поэтому легко посчитать, какой длины должны быть префикс, чтобы на каждый было примерно по 5 хешей) - то можно таблицу префиксов удлинить так, что вместо двоичного поиска можно вставить линейный.
Таблица считается таким кодом:

# на 1 длиннее, чем количество префиксов,
# чтобы всегда был "следующий" для T[high_bits(k) + 1]
T = [None] * (2**K + 1)
j = 0
for i in xrange(2**K):
    T[i] = j
    while j < N and high_bits(K, array[j]) == i:
         j += 1
T[2**K] = N

При поиске ключа k - ищем не в [0, N), а в [T[high_bits(k)], T[high_bits(k) + 1])

Для равномерно распределённых хешей есть ещё интерполяционный поиск, но я привык к табличке, она кажется проще чем корректная реализация интерполяционного поиска. Например про код в ru/en вики я не уверен, что он без зависаний обрабатывает случайные/злонамеренные отклонения от равномерности. Когда я думаю как этот код сделать надёжным, то думается про double-арифметику с квадратными корнями, для поиска интервалов которые "скорее всего" содержат искомый элемент, с удвоением размера интервала, или препроцессинг "максимальное отклонение искомого элемента от расчетной позиции".

Оставить комментарий

Популярные посты:

• Архив