Алгоритмы на JS #1: бинарный поиск
Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) - классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Автор курса, Виктор Карпов (vitkarpov.me/), показывает как этот алгоритм работает и демонстрирует его эффективность через сервис JSPerf.
Важность алгоритмизации в серьезной работе программистом сложно переоценить. На определенном этапе это становится само собой разумеющимся инструментом. И хотя, в зависимости от характера деятельности, веб-разработчик с этим может никогда и не столкнуться. Однако, знание таких вещей дает возможность встать на ступеньку выше и начать создавать ощутимо более сложные и интересные продукты.
Телеграм-канал Виктора: t.me/coding_interviews
⚛️⚛️⚛️
Пройди практический курс "Javascript Fullstack разработчик" от MakeWeb.me.
Детали тут: makeweb.me/course-js-fullstac...
Телеграм для связи по курсу: @makewebchatme
🛍 🛍 🛍
Поддержи проект и получи скидку 5% на 1-ю оплату хостинга/домена Reg.ru.
Промо-код: 948E-53B9-CF98-8204 (вводится во время оплаты услуги).
💬 💬 💬
Присоединяйся к нашему Telegram-чату t.me/makewebme
Пікірлер: 61
⚛⚛⚛ Пройди практический курс "Javascript Fullstack разработчик" от MakeWeb.me. Детали тут: makeweb.me/course-js-fullstack-developer Телеграм для связи по курсу: @makewebchatme
Спасибо за качественный и полезный контент!
Спасибо! Чётко, ясно и понятно!
Долго искала нечто такое! Спасибо вам! Это действительно качественный контент :3
Спасибо за работу, очень полезные уроки!
Это лучшее, что я встречал про алгоритмы. огромное спасибо
Супер. Жду не дождусь видео по другим алгоритмам
То шо надо! Давно пора бы появиться на русском ютубе подобным видео. Немного больше разжевывания не помешало бы, но в целом подача материала хороша и голос приятный. Спасибо, лайк!
Ты крут!) Спасибо за тему алгоритмов с использованием JS! Можно еще продолжения этих уроков?
@MakewebMeOfficial
3 жыл бұрын
Спасибо, надеюсь полезно! Будем продолжать.
Супер круто, спасибо.
Только как неделю начал изучать JS, посмотрев видео сначала ничего не понял, посмотрел второй раз мало что понял, посмотрел видео на след. день и меня просветило, наконец-то понял! Вот только с определением сложности задачи пока туго, пересмотрю видео через время, может тоже просветит)
Очень интересно
ты очень крутой!!!!! Спасибо за видео(начала разработку на js, с этого урока понятно, как структурировать и изучать информацию)
четко все объяснили :)
Всем привет! Автор видоса здесь 👋 Если есть желание подробнее разобраться в бинарном поиске на практических примерах, я сделал плейлист с решениями задачек с LeetCode на эту тему - kzread.info/head/PLtRFPaw3fD5647YtyPCXcuVlGOUrMBgks PS. У меня на канале каждый вторник, в 20 по Мск, проходят стримы с решениями алгоритмических задач. Welcome!
Уважаемый, ты хорош. Благодаря тебе я только что понял бинарный поиск, за два года карьеры.) Если непонятно кому, советовал бы выполнять код в голове - просчитывать значения переменных на каждом шаге, хотя бы условно. А если непонятны логарифмы, то просто запомнить принцип - некоторые стандартные алгоритмы хороши для огромных отсортированных массивов.
@algoseekee
3 жыл бұрын
Спасибо за фидбек. Запилил специальный тредик про логарифм в твитере - twitter.com/vitkarpov/status/1342828952113577984
Я так понимаю, подобные примеры и объяснения взяты из книги "Грокаем алгоритмы". Подача хорошая и интересная)) спасибо)
спасибо добавил в спонсорблок рекламу . просьба проголосовать
Здравствуйте, а я не очень понимаю какая в итоге получится сложность последней функции? Я так понимаю О(N*logN) - это сложность встроенного метода sort и О(logN) это сложность бинарного поиска, опустив ее получается можем сказать, что общая сложность - О(N*logN) ?
) чего только разработчики высокоуровневых языков не сделают лишь бы не работать на работе. Для поиска есть .find Для фильтров есть .filter Также есть .some .indexOf и прочее. В браузерах обычно мы не пишем ракеты летящие на Марс.
@MakewebMeOfficial
3 жыл бұрын
Всё верно. Противоречий нет.
@arh_arh
2 жыл бұрын
ну ведь нужно понимать, как это работает под капотом.
Круууууть! Прекрасная тема. Я этим в свое время занимался, только на 1С и я реализовывал разные сортировки. Единственное я не понял: почему второй вариант называется бинарным?
@algoseekee
4 жыл бұрын
Какой именно вариант? Второй была задача подсчёта частоты вхождений, есть вариант её решения с помощью бинарного поиска - как демонстрация где может использоваться бинарный поиск.
Только начинаю знакомство с алгоритмами. Вопрос относительно бинарного поиска. Понятно, что он эффективнее линейного, но сама сортировка та еще задача. Почему опускается алгоритм сортировки при сравнении? Это как сравнивать соленое с квадратным.
@MakewebMeOfficial
3 жыл бұрын
Хороший вопрос, спасибо. В видео говорится, что прежде чем запускать бинарный поиск требуется выполнить сортировку, соответсвенно всё зависит от того сколько этих самых поисков предполагается выполнить. Если нужно найти элемент всего один раз - нет смысла сортировать, проще линейный поиск запустить, но если поиск нужно выполнить миллион раз, имеет смысл сперва потратить время на сортировку. Где этот самый порог - зависит от конкретного случая, поэтому в реальном проекте имеет смысл профилировать.
Добрый день, подскажите, как переписать данный поиск чтобы он искал не только точный элемент но и больше\равно. Например: Есть массив [5,10,15,38,49,104]. И если попытаться найти элемент, скажем 18 чтобы возвращало индекс числа 49, если 14 то индекс 15. То есть не только элемент но и >= элемент. Спасибо
@MakewebMeOfficial
3 жыл бұрын
То, о чем вы говорите похоже на upper_bound. Можно, например, вот так: codepen.io/vitkarpov/pen/ZEpVKPx?editors=0010
почему left = -1? равзе он не начнет с конца массива?? так же как и arr.length
@user-hm1oc9ze2h
7 күн бұрын
тоже не понял почему -1, а не 0
Вот тут я показывал живой пример реализации двоичного поиска на микроконтроллере: kzread.info/dron/ETNBYBk4IA0rSHCnp2jnhQ.html
А почему return -1 пишется не в else, например?
@cherniaev
3 жыл бұрын
Else избыточен. Если условие выполнится, то функция вернет результат и строки дальше выполняться не будут. Зачем писать больше? Например, такие записи идентичны: 1). if (condition) { return true; } else { return false; } 2). Скобочки для однострочного условия можно тоже опустить. if (condition) return true; return false; В коде из видео я не увидел return -1 после условия, только после цикла. Но, надеюсь, я правильно понял ваш вопрос. Успехов!
@VladimirDevyatoff
3 жыл бұрын
@@cherniaev спасибо
странно бинарный поиск работает только с сортировкой num.sort((a, b) => a - b);
@MakewebMeOfficial
3 жыл бұрын
В этом вся суть алгоритма. Если массив не отсортирован, то нет никакой возможности понять при делении пополам искомое значение слева или справа.
Я бы теорию добавил, практика для начинающих быстровата.
У сортировки сложность больше чем O(n).
Спасибо. Если 95% не понял, что посоветуете? Хотя JavaScript очень нравится и хочу на нем код профессионально писать.
@user-yz6ng4kw4x
4 жыл бұрын
Почитай как нибудь на досуге книжку "Грокаем алгоритмы" там про все популярные алгоритмы (вкл. бинарный поиск) рассказывается максимально простым языком
@MishaWS
4 жыл бұрын
@@user-yz6ng4kw4x Спасибо. На днях купил эту книгу. Читаю на стр.20 Что необходимо знать Чтобы читать эту книгу, необходимо знать базовую алгебру. Например, возьмем следующую функцию: f(x) = x * 2. Чему равен результат f(5)? Если вы ответили "10" - читайте спокойно. Если бы эта простая задачка была задана на JavaScript, я бы ее решил быстро. Но с алгеброй все очень плохо (школа давно в прошлом, уже 43 :) ). Чтобы построить алгоритмы, нужно на отлично алгебру знать? Или алгоритмы это must have только если продукт надо кодить?
@user-yz6ng4kw4x
4 жыл бұрын
@@MishaWS Чтобы строить алгоритмы, достаточно обладать логическим мышлением, не более того. А все классические алгоритмы, которые приводятся в книги, нужны по сути для работы с большими данными (не big data science) для быстрой сортировки и нахождения правильного результата
@algoseekee
3 жыл бұрын
Привет. Можно начать с kzread.info/head/PLtRFPaw3fD55QtDdLVruhKa0M9Wv1l3SR где я разбираю всё с нуля и очень-очень подробно.
Р
Я так понял это не для новичков, а кто давно в теме?!)) Потому что все пишут: «хорош объяснил! Все понятно», только я нечего не понял))))
@MakewebMeOfficial
3 жыл бұрын
Если вы сформулируете вопрос, мы попробуем на него ответить :-)
Мозг.
зачем давать уроки с неправильными решениями ? ваши уроки только вредят тогда а не помагают), в примере все будет работать только если нет повторяющигся елементов, например найти в масиве [1, 56, 2, 3, 4, 5, 3, 2, 6, 7, 56, 8]; 56 даст -1 )) , вот првильное решение: function binarySearch(value, list) { let left = 0; let right = list.length - 1; let position = -1; let middle; while (left value) { right = middle - 1; } else { left = middle + 1; } } return position; }
@algoseekee
4 жыл бұрын
Спасибо за комментарий, выходит вы пытались проверить этот код и разобраться - а говорите видео бесполезные :-) Не очень понимаю пока что не работает, давайте на конкретном работающем коде проверим - codepen.io/vitkarpov/pen/XWmjzMp , вот код из видео на вашем примере, показывает мне что 56 находится под индексом 10. Что именно не работает?
@algoseekee
4 жыл бұрын
Более полный набор тестов можно найти здесь - leetcode.com/problems/binary-search/ . Давайте проверим там.
@algoseekee
4 жыл бұрын
Другой вопрос, что если элементы повторяются, то вообще говоря получаем неопределённое поведение - то ли один найдётся, то ли другой.
@samogray86
4 жыл бұрын
Viktor Karpov Да но находит ближащий елемент, а так вобще не находит, тогда нужно в видно уточнить что пример работает только с таким типом списка, где только уникальние числа.
@algoseekee
4 жыл бұрын
@@samogray86 так стоп, а почему вы пытаетесь применить бинарный поиск на несортированном списке? это так не работает :-) и мой пример выше невалидный, про неопределенное поведение, так просто нельзя алгоритм использовать.