Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
Если внимательно читали статью, там ссылка на Википедию с корректной реализацией.
По-моему тут в статье совсем о другом речь — а именно — не о конкретной реализации, а о том как же ее написать без использования тестирования.
Очень интересно — за 20+ лет программинга — не встречался с «инвариантом цикла». И если это действительно поможет решить эту задачу без тестирования — это очень-очень интересно.
Написано, конечно, сложно, перечитываю уже который раз, пытаюсь вникнуть.
Очень интересно — за 20+ лет программинга — не встречался с «инвариантом цикла». И если это действительно поможет решить эту задачу без тестирования — это очень-очень интересно.
Написано, конечно, сложно, перечитываю уже который раз, пытаюсь вникнуть.
«Aj: 1 <= j < L или U < j <= N: X[j] != T»
А можно тут пояснения в текст добавить?
Что такое «Aj»?
Что такое «j»?
Куда делать область «О»?
И как-то надо тут расставить скобочки, а то не понятно:
то ли «Aj = ( (1 <= j < L) или (U < j <= N)); X[j] != T;»
то ли «Aj = ( ((1 <= j < L) или (U < j <= N)) И (X[j] != T))»
то ли еще что-то…
А можно тут пояснения в текст добавить?
Что такое «Aj»?
Что такое «j»?
Куда делать область «О»?
И как-то надо тут расставить скобочки, а то не понятно:
то ли «Aj = ( (1 <= j < L) или (U < j <= N)); X[j] != T;»
то ли «Aj = ( ((1 <= j < L) или (U < j <= N)) И (X[j] != T))»
то ли еще что-то…
Да читал, конечно. Код приведен просто для полноты картины, иначе была бы какая-то незаконченность.
Спасибо за статью. Будет кармы достаточно — перенесите лучше в публичный, например в "Алгоритмы" — больше людей увидит.
Шикарно! 10 минут осмысления. 5 минут рисования на бумажке и задача становится тривиальной!
Помимо сохранения инварианта важный элемент реализации — конечность времени работы. В вашем коде это гарантируется постоянным уменьшением интервала либо установкой флага found, но в самой статье об этом моменте практически ничего не сказано. А между тем на моей памяти большинство неправильных реализаций двоичного поиска именно зависали, а не выдавали неверный ответ.
читал читал, но так и не вкурил, насколько это объяснение проще чем «охота на льва методом дихотомии»?
а вообще странно это. я по образованию не программист ни разу, про то что «двоичный поиск» это нечто фундаментальное не слышал ни разу, даже термин такой не знал до недавнего времени, но подобные задачи кажутся тривиальными. возможно это потому что когда нам читал курс «вычислительных методов… бла-бла… матеметике» мне попалась отличная книжка с кучей разобранных алгоритмов и реализацией на фортране…
а вообще странно это. я по образованию не программист ни разу, про то что «двоичный поиск» это нечто фундаментальное не слышал ни разу, даже термин такой не знал до недавнего времени, но подобные задачи кажутся тривиальными. возможно это потому что когда нам читал курс «вычислительных методов… бла-бла… матеметике» мне попалась отличная книжка с кучей разобранных алгоритмов и реализацией на фортране…
И при этом вы затратили в 2 раза больше сравнений. А все дело в том, что вы мыслите в человеческих терминах, а не в компьютерно-математических. Наилучший объект для разбиения на 2 части с точки зрения математики — полуоткрытый интервал. Алгоритм становится таким (для 0-based массивов):
// бинарный поиск, который ищет не только элемент, но и границу снизу.
L=0;R=N;
if (T<a[0]) //во многих случаях априори известно, что a[0]<=T и это можно опустить
{
lindex=-1;
found=false;
return;
}
// invariant: a[L]<=T<a[R] где a[N]=бесконечность
// реального обращения к a[N] нет.
while (R-L>1)
{
M=(R+L)/2;// если массивы не длиннее миллиарда элементов
if (T<a[M])
{
R=M;
}else //a[M]<=T
{
L=M;
}
}
lindex=L;
found=a[L]==T;
для массива длинной 2 и искомым элементом на 1й (не 0й) позиции работать не будет + все случаи которые сводятся к этому. видимо иногда полезней мыслить в человеческих терминах :)
Вы выбрали неудачный инвариант. В книге Вирта «Algorithms and Data Structures» www-old.oberon.ethz.ch/WirthPubl/AD.pdf (есть русский перевод www.ozon.ru/context/detail/id/4803785/ ) используется такой инвариант:
(Ak: 0 <= k < L: a[k] < T) & (Ak: R <= k < N: a[k] >= T)
Т.е., не a[L], а a[R] может быть равно T.
Тогда не требуется дополнительный анализ перед циклом:
(Ak: 0 <= k < L: a[k] < T) & (Ak: R <= k < N: a[k] >= T)
Т.е., не a[L], а a[R] может быть равно T.
Тогда не требуется дополнительный анализ перед циклом:
L:=0;R:=N;
WHILE L < R DO
m:=(L+R) DIV 2;
IF a[m] < T THEN
L := m+1
ELSE
R := m
END
END
1) обычно инвариант цикла определяется как условие верное перед каждой итерацией цикла.
«истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла» — вовсем непонятно, потому что можно подумать что условие верно всегда. но обычно инвариант цикла может нарушаться в теле, лишь бы он был верен перед очередной итерацией.
2) добавьте в статью пару слов о том что лучше бы еще чтоб инвариант гарантировал что цикл завершится. в идеале должна быть некая мера, которая должна уменьшаться с каждой итерацией цикла
3) перенесите в подходящий блог. статься полезна многим, а так ее почти никто не прочитает
«истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла» — вовсем непонятно, потому что можно подумать что условие верно всегда. но обычно инвариант цикла может нарушаться в теле, лишь бы он был верен перед очередной итерацией.
2) добавьте в статью пару слов о том что лучше бы еще чтоб инвариант гарантировал что цикл завершится. в идеале должна быть некая мера, которая должна уменьшаться с каждой итерацией цикла
3) перенесите в подходящий блог. статься полезна многим, а так ее почти никто не прочитает
Для тех кто заинтересовался можете почитать книжку Шеня «Программирование: теоремы и задачи», там про инвариант цикла рассказывается в самом начале, а дальше много чего еще интересного.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как же все-таки правильно написать двоичный поиск?