Pull to refresh

Comments 23

Если внимательно читали статью, там ссылка на Википедию с корректной реализацией.
По-моему тут в статье совсем о другом речь — а именно — не о конкретной реализации, а о том как же ее написать без использования тестирования.

Очень интересно — за 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))»
то ли еще что-то…
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Пипец. Это же надо было автору так ужасно написать…
Здорово изобразили, спасибо.
Надо бы подправить статью, но можно ли сделать это задним числом? А то вдруг какой-нибудь дубль появится.
UFO just landed and posted this here
Да читал, конечно. Код приведен просто для полноты картины, иначе была бы какая-то незаконченность.
Спасибо за статью. Будет кармы достаточно — перенесите лучше в публичный, например в "Алгоритмы" — больше людей увидит.
UFO just landed and posted this here
Шикарно! 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й) позиции работать не будет + все случаи которые сводятся к этому. видимо иногда полезней мыслить в человеческих терминах :)
Почему не будет? Изначально L=0, R=2. M будет выставлено равным 1. Поскольку этот элемент искомый, то T<a[1] не верно и мы получим L=M=1. В конце мы сравним a[1] и T и получим, что они совпадают как и положено. lindex будет равен L=1, как и требовалось.
ваша правда. будет. видимо сонный был :)
Вы выбрали неудачный инвариант. В книге Вирта «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.
Тогда не требуется дополнительный анализ перед циклом:

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) перенесите в подходящий блог. статься полезна многим, а так ее почти никто не прочитает
Для тех кто заинтересовался можете почитать книжку Шеня «Программирование: теоремы и задачи», там про инвариант цикла рассказывается в самом начале, а дальше много чего еще интересного.
Еще есть старая советская книга Кушниренко, Лебедев «Программирование для математиков». По-моему там глава целая посвящена циклам и инвариантам
Sign up to leave a comment.

Articles