Comments 26
Хорошая статья, подробная (даже слишком 😁)
Можно было бы пойти дальше, и сказать, что в вашем коде, при наличии нескольких искомых чисел в массиве, будет находиться рандомный индекс из блока одинаковых чисел (в том смысле, что результат на разных массивах будет разный, где-то вы вернете первое число, где-то среднее, где-то последнее, итд). Можно было бы подумать/написать, как изменить код так, чтобы находился всегда первый/всегда последний, и при запуске обоих вариантов, вообще отрезок (:
Просто это на самом деле, было бы читать интереснее, чем про то, как устроена память компьютера. Те кого интересует бин. поиск, имхо и так это уже должны понимать
Спасибо)
Да, полностью согласен что материал очень простой.
Дело в том, что я сам не профи в алгоритмах, и хочу давать материал последовательно. Изначально статья была нацелена на тех кто в принципе не знаком с алгоритмами, либо не вдавался в подробности работы массива - таких людей на самом деле очень много.
В любом случае с ростом моих знаний и интересов, последующие публикации будут расти как по сложности, так и по интересу (за счет той же сложности)
Очередная статья от школьника/студента? Зачем это на Хабре? Тем более, что там в нескольких местах неверные утверждения (или грубые допущения).
P. S. И уже что-то свое на Гитхабе, и уже свой телеграм-канал... Я фигею, дорогая редакция.
Может лучше укажете где грубые допущения/неверные утверждения? Да, статей про бинарный поиск большая куча, но может, именно эта статья, поможет кому-то лучше понять бин. поиск, а если кто-то его уже знает/ему не интересно, то просто не будет читать?
Ну хотя бы то, что время доступа к элементу не одинаковое. Если элемент массива ни в одном из кешей, то время доступа увеличивается раз в сто. А если это не элемент данных, а ссылка на объект, то время доступа может ещё удвоиться.
Во всех известных мне языках программирования, время доступа к элементу обычного массива — константа, с точки зрения О-нотации. Поэтому это не имеет значения, а вы просто пытаетесь умничать, извините
Тем не менее, современные процессоры сломали представления о давно известных алогоритмах.
Ну тогда с нетерпением жду примеров. Ну и даже если так, то бинарный поиск уж точно не входит в их число. Я сдал приличное число задач на бин. поиск, что на литкоде, что в других местах, и на разных языках. Ни разу не столкнулся даже с намеком на то, что О-нотация посчитанная до сдачи задачи, разошлась бы с реальностью.
И еще, поправьте меня пожалуйста, возможно я плохо прочитал статью, но где в ней говорится, что время доступа к элементу одинаковое, как вы упомянули в самом начале? Я нашел лишь, что доступ к элементам происходит за константное время, вы с этим не согласны? Хотите сказать, что существуют какие-то супер модные процессоры, про которые видимо знает ОЧЕНЬ ограниченный круг людей, в которых время доступа к элементу массива зависит от его размера? Даже если время увеличивается "раз в сто", или даже в 200, это по прежнему остаётся константой (с точки зрения О-нотации). Так что зря вы жалуетесь на такие статьи, оказывается даже вам, есть что подчерпнуть из них, хоть и в комментариях
С нетерпением жду плюса в карму и примеры последуют. Нет, там именно так и написано - всегда одинаковое.
Что могу ответить.. В любом случае спасибо за комментарий, он помогает продвижению публикации)
Не хочу отвечать хейтом на хейт, отвечу по-доброму, с уважением, хоть Вы ко мне его и не проявили)
Высказывание про школьника или студента выглядит как оскорбление, мол "Вот я опытный программист, у меня 30+ лет опыта, а ты сопляк, мне тут что-то будешь обьяснять".
Зачем это на Хабре - вопрос очень странный. Я написал статью, где поделился подробным и простым разбором алгоритма, а также привел понятные иллюстрации для лучшего усвоения) Статья ориентирована на новичков, либо на людей которые никогда не интересовались темой алгоритмов или слабо представляют как это работает.
Несмотря на то, что статья простая по своему изложению и сути - я вложил в нее много времени и сил, чтобы привести понятные примеры и приложить приятные глазу иллюстрации, демонстрирующие принципы чуть лучше.
Если вам не интересна публикация - просто не тратьте свое время на ее прочтение, тем более в самом начале я выделил основные компоненты, которые будут разбираться.
Насчет гитхаба - считаю писать свои проекты хорошей практикой - мне нечего скрывать, мой код и стиль написания доступен всем.
Упоминание моего телеграм-канала никого не призывает туда переходить. Это сделано для того, чтобы люди, которым нравится моя манера изложения, смогли посмотреть другие мои публикации и следить за мной не только здесь, но и на других платформах. Или вы что-то имеете против?)
Публиковать такой текст на Хабре, это как написать текст про "как научиться плавать" в чате любителей и профессионалов плаванья. Не просто текст по алгоритму, но с разжевыванием деталей и аналогиями на уровне детей.
Недавно один подробно писал тут, чем бит от байта отличается. Зачем тут это всё??
Стоит ли добавлять проверку "если таргет больше последнего числа ИЛИ меньше первого: возвращаем -1"? Тогда нам не придется ждать пока цикл пройдет по всему массиву. Позволит ли это сэкономить время (пусть и совсем крохи)?
Написать кучу букв про бинпоиск и не упомянуть upperbound/lowerbound - зря время потратить.
Да не про бинпоиск, а про кинозал.
Не, ну сам по себе бинпоиск разобран, тут без вопросов. Только реализовывать нужно именно как upperbound/lowerbound. Во-первых, потому что это задача в общем виде, а поиск элемента - частный случай. Во-вторых, на каждой итерации на одно сравнение меньше, в самих итераций - лишь на одну больше в среднем случае (у представленного здесь поиска элемента делается выход из цикла, если элемент нашелся, до полного сужения интервала, но в среднем случае это будет на предпоследней итерации). Иными словами, писать "поиск элемента" - то, как не надо делать.
Это пояснение автору, до чего именно я так душно докопался.
Писать алгоритмы надо очень аккуратно, иначе можно погореть на граничных случаях.
Например, у вас не работает поиск на массиве из одного элемента.
search(new int[]{99}, 99);
вернет -1
Создать массив размерности n = 15, зарезервировав тем самым память под этот массив...
Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива. В приведенном примере речь идет о размере массива, но не о его размерности. Исправьте, пожалуйста.
Бинарный поиск на пальцах