|
SergLet wrote:
> про описание алгоритма двоичного (бинарного) поиска ? Чего то не могу
> ничего внятного найти!
Захотелось поделиться. Долго не понимал алгоритм, и приходилось
постоянно нырять в литературу. Но после того, как один раз понял
принципы все оказалось просто до безобразия.
Двоичный поиск работает последовательным сужением интервала [A,B], до
тех пор, пока этот интервал не окажется пустым. Теперь самая важная
вешь: из определения интервала видно, что элемент с индексом A - это
первый элемент, который *может* оказаться искомым. А элемент с индексом
B - это последний элемент, который *может* оказаться искомым. Понимая
все это, весь алгоритм воссоздается в нужной форме самой простой логикой:
Инициализация: A указывает на первый элемент, B на последний элемент.
Поиск: Возьмем любой элемент лежащий в интервале [A,B], обозначим его C,
и сравним этот элемент с искомым значением. Очевидно, что у нас будет
три случая:
0) Равенство - тривиальный случай.
1) Если искомое значение меньше элемента C, то, очевидно, что нужный нам
элемент находится между A и C. Причем, про C мы уже знаем, что он точно
не является искомым, то есть - верхней границей будет элемент,
предшествующий C. Сужаем интервал до состояния [A,C-1].
2) Искомое значение больше C. Очевидно, что искомый элемент находится
между C и B, причем C так-же не является искомым. Значит, сужаем
интервал до состояния [C+1,B].
Элемент C можно выбирать по разному (например, в некоторых задачах
быстрее работает золотое сечение), но из общих соображений быстрее
разбивать интервал каждый раз пополам.
И вообще - варианты поиска очевидным образом вытекают из определения
интервала. Скажем, исключение отдельного случая равенства (0), чтобы
оставить одно сравнение, достигается изменением случая (2) - при этом
искомое значение больше либо равно C. А значит, элемент C *может* быть
искомым значением - сужаем до интервала [C,B].
Если последовательность содержит не уникальные значения, что мы, деля
интервал в произвольной точке, можем попадать не на границу
подпоследовательности. Приведенный алгоритм с сохранением случая
равенства, будет находить любой элемент подпоследовательности, при
исключении равенства, будет находить первый элемент
подпоследовательности. Тривиально изменяя обработку результатов
сравнения, мы можем находить последний элемент подпоследовательности.
Иногда удобны другие определения интервала. Например, интервал [A,B),
такой, что A - первый элемент, который может оказаться искомым, а B -
элемент который точно не является искомым. Тогда, из рассуждений
подобных приведенным строится обработка результатов сравнения.
Posted via ActualForum NNTP Server 1.4
|
