Если нет промежутков, то у нас получается что-то вроде: [0, 1, 2, 4, 5] и 3, ну и куда вставлять - как бы очевидно... Ну, по крайней мере это то, что я имел в виду.
А по поводу сложно - ну так наверняка, если сложно самому, то есть в каких-нибудь библиотеках реализовано и проверено...
Код:
(defun binary-search (array finder)
(let ((offset 0)
(step-size (length array))
(minlen (1- (length array)))
(found 1))
(while (and (/= found 0)
(> step-size 0))
(let ((half (ceiling step-size 2)))
(setq step-size half
offset (min (+ offset (* half found)) minlen)
found (funcall finder (aref array offset)))))
(if (= 0 found) offset -1)))
Кстати, на счет "сложности"... В мире есть такое количество гораздо более сложны алгоритмов, чем вот это... и это заняло, ну, примерно час написать и убедиться в работоспособности.
Автор статьи с хабра просто не пробовал реализовать что-то по-серьезнее, вот и плачется :|