Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 23
Простите, а что Вы в бинарном поиске собрались заучивать? Он же прост настолько, что его можно самому с нуля независимо изобрести.
Согласен с Вами. Человеку, которому требуются усилия для понимания бинарного поиска, нечего делать в программировании. Но статья – просто вода чатбота.
С бинарным поиском все понятно, но у новичков возникает проблема в том чтобы закодить решение на собесе. По вашему в программирование попадают люди у которых с рождения есть навыки решения алгоритмических задач на js, для остальных вход закрыт?
Вход не закрыт, но смысла нет.
Да что сложного? Ошибок на единицу понаделать есть где, но остальное пишется быстрее чем эта стена текста читается.
С рождения, конечно такого навыка нет, он появляется в результате практики по решению этих самых алгоритмических задач. Но если человеку это даётся с огромным трудом, и человека интересует в этом вопросе только зарплата, то лучше поискать себя в другой сфере деятельности
Насколько я могу судить, статья – типичное "пока объяснял, сам разобрался". Она нужна автору, а не сообществу.
Мне так на 1м курсе на мат. анализе показалось, что теорема Больцано-Вейерштрасса очень легко доказывается, всего то надо рекурсивно делить отрезок, содержащий бесконечное число точек пополам. Ну по сути тот самый бинарный поиск.
Глупый был, не знал, что если теорема называется именами выдающихся людей, то она не может быть настолько тривиальной.
А на экзамене меня попросили доказать, что среди бесконечного множества этих самых вложенных отрезков, которые я построил, найдется хотя бы одна точка принадлежащая им всем. И тут то я сдулся. Оказывается это вообще невозможно доказать. Ну т.е. можно, если воспользоваться каким либо хитрыми аксиомами о существовании супремума или её эквивалентами, например аксиомой о непрерывносити числового множества. Но я этого не знал, а сам растерялся и не догадался на экзамене до этого, за что и получил трояк.
Если кто-то собрался кого-то учить, то начинать он должен с понятий. Например, в я так и не увидел в статье, что такое бинарный поиск:(. И уж тем более надо описать, что такое открытый и закрытый диапазоны.
Когда сайты делали, просто в шок приходил от клиентов, когда они в свойствах товара писали какие-то отличия от конкурентов, которые понятны только конкурентам. А о том, что сначала товар просто описать надо для пользователя, который просто где-то про него услышал и раздумает, нужен он ему вообще или не нужен, клиент даже не задумывается. Вот и здесь примерно так. Статья понятна для тех, кто и так все знает:)
Интересно почитать, но не осилил - слишком много букв для простого объяснения. Я не запоминаю эти алгоритмы, благо, подумав логически, их можно изобрести заново.
В функциях недостаточная проверка данных. findLeftBoundry и binarySearchHalfOpenInterval вернут Undefined offset, если target больше, чем количество элементов в массиве. Плохо left === arr.length, хорошо left >= arr.length
Благодарю всех за дискуссию и обратную связь.
В ходе обсуждения прозвучали тезисы, которые могут ввести в заблуждение начинающих разработчиков. Считаю важным ответить на них, опираясь на объективные данные.
Приведу несколько фактов:
Задача №34 "Find First and Last Position of Element in Sorted Array", классическое применение бинарного поиска, имеет сложность Medium на LeetCode.
Эта же задача (и её вариации) используется на собеседованиях в крупнейших IT-компаниях, часто как одна из самых сложных на алгоритмической секции.
В стандартной библиотеке Java метод Arrays.binarySearch() почти 10 лет содержал баг с переполнением целого числа. Как отмечает Джошуа Блох (один из ключевых разработчиков Java), даже спустя годы в большинстве учебных материалов продолжает преподаваться именно ошибочная версия алгоритма.
Вывод:
Приведенные факты демонстрируют, что утверждение об "очевидности" бинарного поиска является заблуждением. Подобные заявления неверны по сути и вредны, поскольку демотивируют начинающих специалистов, сталкивающихся с реальными трудностями при изучении этой темы.
Два аргумента от "авторитета". Третий аргумент - про поиск заклёпок. Очевидно, метод содержал эту уязвимость потому, что на практике в массиве никогда не бывает так много элементов, чтобы сумма двух индексов вызвала переполнение.
А вот контраргумент, опираясь на объективные данные: артиллерийская вилка известна спокон веку. И её прекрасно осваивают не программисты, а, прости господи, призывники.
сталкивающихся с реальными трудностями при изучении этой темы.
Назовите хоть одну реальную трудность? Трудно понять "проверь середину, и определи, решение ближе или дальше середины, а потом повтори то же самое для соответствующей половины отрезка"?
Вот вы зачем мне ставите минусы?
Как вы сказали, я привел аргументы от авторитетов. Я их не придумал.
Вы с ними и спорьте, напишите: «Я, Zenitchik, автор 12 тысяч комментариев на Хабре, знаю лучше, чем Джошуа Блох (ключевой разработчик Java) и эксперты LeetCode. Баг с переполнением, который они пропустили, — это не проблема, а сложность задачи на LeetCode — искусственно завышена».
А обратную связь по статье я принимаю, спасибо.
Как вы сказали, я привел аргументы от авторитетов. Я их не придумал.
Ну да. А апелляция к авторитету - это признак невалидного аргумента. Если не сказать, демагогический приём.
А реальную трудность вы так и не назвали.
Давайте разберем то, что вы написали:
Апелляция к авторитету — это признак невалидного аргумента.
А то и демагогический приём.
Ссылка на авторитетный источник сама по себе не делает аргумент невалидным. Он становится таким, если искажать факты, подгонять их под свою точку зрения или что-то выдумывать. Я этого не делал.
Похоже, вы пишете что пишите, потому что не прочитали статью Блоха, которую я уже привел как источник. В ней он рассуждает о сложности алгоритма, упоминая, что прошло почти два десятка лет с появления концепции до её первой стабильной реализации.
Но вместо того, чтобы оспорить эти факты из первоисточника, вы ставите минус и доводите ситуацию до абсурда: заявляете, что ссылаться на эксперта в его же области — это «невалидный аргумент».
Спасибо за комментарии, всего вам доброго!
Ссылка на авторитетный источник сама по себе не делает аргумент невалидным
Нет, не это. А то, что "мнение авторитетного человека" и "авторитетный источник" - это не одно и то же. Сколь угодно авторитетный человек, может ошибиться. Если в источнике предложен метод, которым можно проверить утверждение, то это авторитетный источник. Если нет - то это просто слова.
А когда предлагают поверить человеку только потому, что он авторитетный - это демагогия. В приличном обществе за такое пинают.
В ней он рассуждает о сложности алгоритма, упоминая, что прошло почти два десятка лет с появления концепции до её первой стабильной реализации.
Вы это серьёзно? Артиллерийская вилка так же стара, как нарезная артиллерия. Т.е. концепция двоичного поиска появилась ОЧЕНЬ ДАВНО.
И называть реализацию на Java первой стабильной реализацией - по меньшей мере... странно. Знаете, до Java другие языки были. А до них другие. Вы же не думаете, что для них не было реализации двоичного поиска?
Статью я прочитал, и выше на утверждение возразил. Массивы длиной 4 млрд элементов - это ненаучная фантастика, поэтому ошибка была и остаётся некритичной. Впрочем, хорошо, что её всё-таки нашли и исправили.
Мне кажется, что Вы сами не разобрались толком в алгоритме, а только полагаетесь на чужие слова. Нельзя так делать.
И называть реализацию на Java первой стабильной реализацией - по меньшей мере... странно. Знаете, до Java другие языки были. А до них другие. Вы же не думаете, что для них не было реализации двоичного поиска?
Еще раз прошу прочесть статью, Блох не утверждал, что первая стабильная реализация была на Java. Он разместил цитату Джона Бентли из книги "Programming Pearls": "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962."
Если бы Вы прочитали, наверно бы вы не ошиблись...
Каюсь, читал по диагонали. Похоже, по этому пункту я не прав.
Это просто какая-то демагогия у Бентли. До 1962 года заведомо не было компьютеров, у которых размер физической памяти достигал бы разрядности целых чисел. Поэтому для тех времён сложение было совершенно корректно. А уж то, что разработчики Java некритично заимствовали алгоритм в эпоху гигабайтной памяти – их личная проблема.
Тут же надо заметить, что некоторые языки имеют арифметику неограниченной разрядности.
Без обид, мне кажется, что алгоритм и вправду лёгкий для новичка.
Но я буду рад узнать новое, если вы скажите, в чем трудность этого алгоритма.
И кста, спасибо за статью.
ps. Надеюсь, вы не ответите в стиле "мопед не мой, ..." :)
Конечно, без обид!
Сразу предупрежу, у меня нет 100% уверенности, что статья получилась и она кому-то поможет.
Написал я ее потому, что почти все алгоритмы, где бы я ни смотрел, преподносятся как готовые решения.
У меня была идея, что если проговорить больше, чем обычно, то это может быть полезно новичкам. Показать, каково это — идти по логике алгоритма, до момента, когда он оказывается элементарным.
Есть ли в этом смысл? Я не знаю.
Один скажет, что склонность к программированию должна быть очевидна. Такой новичок всё будет понимать сразу без объяснений.
Но у меня возникают сомнения: а может ли быть когорта людей, которым стартовать сложнее по какой-то причине, но при этом это не уменьшает их потенциальный талант?
И вот меня обвинили в том, что это текст чат-бота. Да, может, получилось не идеально. Но я несколько дней писал и редактировал текст, постарался объяснить то, чего не нашел ни на русском, ни на английском, и добавил подсказки про диапазоны как возможность задуматься о том, как вообще человек пишет и думает о циклах.
Простите, но если человек не понимает объяснение этого алгоритма на пальцах то ему нечего делать в разработке. Не надо понятнее, это не имеет смысла.
Я учился первому языку Кернигану и Ритчи, а алгоритмам по Кнуту. Их книжки все еще лучшие. Для уровня старшей школы или около того, первые курсы тоже ок.
Не смотрите на дату выпуска, с тех пор ничего не изменилось. А чтобы написать книжку все еще требуется талант.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Зубрить сложно, понимать легко: бинарный поиск