OberonCore
https://forum.oberoncore.ru/

Только 10% программистов способны написать двоичный поиск
https://forum.oberoncore.ru/viewtopic.php?f=82&t=2580		 Страница 1 из 2
Автор:  Максим Андреев [ Среда, 21 Апрель, 2010 15:05 ]
Заголовок сообщения:  Только 10% программистов способны написать двоичный поиск
Интересная статья на Хабре: http://habrahabr.ru/blogs/algorithm/91605/#habracut
Вернее, интересна не сама статья, а комментарии к ней.

Первая реакция --- написать двоичный поиск не сложно. Было сразу предложено несколько вариантов реализации. Но, что интересно, среди них нет ни одного 100% верного решения!

После небольшой дискуссии сошлись на том, что программисту знать про двоичный поиск не обязательно :?
Автор:  Peter Almazov [ Среда, 21 Апрель, 2010 15:30 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Если кто-нибудь зарегистрирован на Хабре, киньте туда эту ссылку viewtopic.php?p=46182#p46182
Удалено модератором
Автор:  bohdant [ Среда, 21 Апрель, 2010 16:39 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Интересно, вот написал, "распространенных ошибок" вроде нет.
Интересно, есть ли ошибки?

Код:
MODULE BinSearch; (** AUTHOR ""; PURPOSE ""; *)
IMPORT KernelLog;
PROCEDURE Search(x:LONGINT; a:ARRAY[*] OF LONGINT):LONGINT;
VAR
 n1,n2,i:LONGINT;
BEGIN
   n1:=0;
   n2:=LEN(a)-1;
   IF n2<0 THEN RETURN -1 END;
   i:=(n2-n1) DIV 2;
   WHILE (x#a[i])&(n1#n2) DO
      IF (x>a[i]) THEN
         IF (i#n1) THEN
            n1:=i;
         ELSE
            n1:=n2
         END;
      ELSE
         n2:=i;
      END;
      i:=(n2-n1) DIV 2+n1;
   END;
   IF (x=a[i]) THEN
      RETURN i;
   ELSE
      RETURN -1;
   END;
END Search;

PROCEDURE Test*;
BEGIN
KernelLog.String("Res= ");KernelLog.Int( Search(0,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(1,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(2,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(3,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(4,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(5,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(2,[1,2]), 0); KernelLog.Ln;
END Test;

END BinSearch.Test~
Автор:  Info21 [ Среда, 21 Апрель, 2010 16:50 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Коллеги, вы бы лучше выучили второй вариант двоичного поиска из Алгоритмов... Вирта. Он и проще, и эффективней. Там ищется не a[i]=x, а такое i, что для всех j<i a[j]<x, и для всех j>=i a[j]>=x. Начало i=0, j=LEN. Охрана цикла i<j. В конце одна доп. проверка, имеет ли место a[i]=x. Тело цикла профессионалы заполнют сами, надеюсь. А остальные прочтут :)
Автор:  bohdant [ Среда, 21 Апрель, 2010 16:59 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Info21 писал(а):
Коллеги, вы бы лучше выучили второй вариант двоичного поиска из Алгоритмов... Вирта.

Выучить всегда можно, а тут как кроссворд решить - просто интересно :wink:
PS: а за совет спасибо!
Автор:  AVC [ Среда, 21 Апрель, 2010 17:29 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Интересно, а в той версии 1962 года, которую Кнут признал корректной, как вычислялся индекс среднего элемента? :roll:
Автор:  Info21 [ Среда, 21 Апрель, 2010 20:29 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
bohdant писал(а):
PS: а за совет спасибо!
На самом деле тут штучка гораздо интересней любого кроссворда: подмена конечного условия более слабым.
Обычно с другой стороны мысль идет, причем инерция очень сильна.

Уже год эту штучку в голове верчу, пытаюсь к другим задачам как-нибудь научиться припаивать...
Автор:  Peter Almazov [ Четверг, 22 Апрель, 2010 05:36 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Info21 писал(а):
На самом деле тут штучка гораздо интересней любого кроссворда: подмена конечного условия более слабым.
Обычно с другой стороны мысль идет, причем инерция очень сильна.
Обратите внимание, что приведенная мной ссылка содержит эту штучку для инварианта: у Вирта описывается инвариант, где один кусок области содержит значения меньшие х, а другой - большие х. Я привел более слабый - область из двух кусков не содержит х.
Автор:  Info21 [ Четверг, 22 Апрель, 2010 10:16 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Peter Almazov писал(а):
у Вирта описывается инвариант, где один кусок области содержит значения меньшие х, а другой - большие х. Я привел более слабый - область из двух кусков не содержит х.
Почему же более слабый: речь об упорядоченном массиве.
Автор:  Info21 [ Четверг, 22 Апрель, 2010 10:21 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
И по поводу структурного подобия линейному поиску:
там имеет место быть частично упорядоченная по включению система интервалов, потенциально содержащих искомый элемент.
В этой системе единственная "точная нижняя грань".
Поэтому если мы ищем ее, то любой путь по стрелочкам будет корректным.
Чем и обуславливается "фундаментальное структурное подобие".
Автор:  Peter Almazov [ Четверг, 22 Апрель, 2010 16:07 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Это опять анализ. Вы про синтез напишите.
Автор:  Info21 [ Четверг, 22 Апрель, 2010 16:31 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Peter Almazov писал(а):
Вы про синтез напишите.
Так программа в книжке была выстроена -- как? :)
Вон и bohdan ту же логику применил.
Автор:  Peter Almazov [ Четверг, 22 Апрель, 2010 16:58 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Info21 писал(а):
Peter Almazov писал(а):
Вы про синтез напишите.
Так программа в книжке была выстроена -- как? :)
Вон и bohdan ту же логику применил.
1. Какая конкретно программа?
2. И как же она была выстроена? Самое главное, кем выстроена?
3. bohdant применил не логику, а гадание на кофейной гуще.
Автор:  Info21 [ Четверг, 22 Апрель, 2010 17:24 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Peter Almazov писал(а):
Info21 писал(а):
Peter Almazov писал(а):
Вы про синтез напишите.
Так программа в книжке была выстроена -- как? :)
Вон и bohdan ту же логику применил.
1. Какая конкретно программа?
Мы вроде с самого начала обсуждаем двоичный поиск.
В простом ЛП ищем, перебирая подряд.
Здесь ищем, беря случайный элемент в сужающихся интервалах, с гарантией сходящихся к цели.
Как только это замечено, сразу пишется цикл.
Следуя шаблону линейного поиска :)
Чё тут синтезировать, когда шаблон уже есть :)
Автор:  Peter Almazov [ Четверг, 22 Апрель, 2010 18:12 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Info21 писал(а):
Мы вроде с самого начала обсуждаем двоичный поиск.
В простом ЛП ищем, перебирая подряд.
Здесь ищем, беря случайный элемент в сужающихся интервалах, с гарантией сходящихся к цели.
Как только это замечено, сразу пишется цикл.
Следуя шаблону линейного поиска :)
Чё тут синтезировать, когда шаблон уже есть :)
В общем, все понятно.
Спасибо за ответы.
Автор:  bohdant [ Четверг, 22 Апрель, 2010 18:18 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Peter Almazov писал(а):
3. bohdant применил не логику, а гадание на кофейной гуще.

хм... новый стиль программирования "гадание на кофейной гуще"? Да нет, я пробовал применить логику, только свою, а не чужую. Мозги нужно иногда тренировать, а то если все будет писатся на шаблонах то мы прийдем к стогнации.
Петр, если Вас послушать, то программисты нынче должны все делать по книгам (или по гуглу), своими мозгами шевелить запрещено.
Давайте вспомним сколько раз переделывал Брезенхейм свой алгоритм построения линии? Неужто до него не было ничего?
Автор:  Peter Almazov [ Четверг, 22 Апрель, 2010 18:45 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Да ладно, не обижайтесь :)
Я вот подредактировал свой пост про двоичный поиск, и послал на habrahabr.ru. Модераторы одобрили публикацию.
Как же все-таки правильно написать двоичный поиск?
Автор:  delphiec [ Суббота, 24 Апрель, 2010 12:08 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
Написать на бумаге возможно и 10%, но думается при 99% вероятности ошибки.

В процессе отладки обнаруживаются ошибки (пропуск правого и левого крайних индексов, пропуск среднего индекса), переполнение при делении на 2, но после некоторых размышлений сложение не трудно поменять на вычитание.

Много времени занимает отладка. Думается, что свойство "способность" дано не корректно. Во-первых, программист имеет возможность отладки, а во вторых неограниченное время. Эти условия в счет не принимаются.

Сам факт, достаточно трудного обнаружения ошибки при "новых условиях", говорит о том, что нужно внимательно относиться к тестам.
Автор:  Info21 [ Суббота, 24 Апрель, 2010 17:55 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
delphiec писал(а):
Много времени занимает отладка.
Отладка? В этом алгоритме? No comment.
Автор:  Валерий Лаптев [ Суббота, 24 Апрель, 2010 20:34 ]
Заголовок сообщения:  Re: Только 10% программистов способны написать двоичный поис
delphiec писал(а):
Написать на бумаге возможно и 10%, но думается при 99% вероятности ошибки.
Много времени занимает отладка.

В том то и дело, что такой алгоритм должен быть написан сразу правильно - никакой отладки тут не требуется. Если знаешь шаблон поиска.
Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/