Binary Search Algorithm | JavaScript
HTML-код
- Опубликовано: 23 фев 2021
- Друзья, этим видео мы начинаем долгожданную рубрику Алгоритмов и Структур данных.
Сегодня мы с вами рассмотрим один из самых известных и часто встречающихся на фронтенд-собеседованиях алгоритмов - Бинарный поиск. Его также называют Двоичный поиск.
Он позволяет найти необходимое в массиве из миллиона элементов всего за 20 итераций. Важный момент: этот алгоритм работает только на отсортированных массивах данных.
Кроме самого принципа работы алгоритма, мы также с вами напишем нашу с вами реализацию поиска элементов в массиве на JavaScript.
Приятного просмотра!
Обязательно оставляйте в комментариях свои пожелания, какие алгоритмы именно вы хотите увидеть на нашем канале.
Поделитесь этим видео с друзьями и поставьте нам красивый лайк!
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-science.com/
#BinarySearch #БинарныйПоиск #алгоритмы #frontend #itсобеседование #ityoutubersru
Я бы хотел разобрать все самые известные алгоритмы, можно прям с книги грокаем алгоритмы, там и про графы, Дейкстры и т.д, можно было бы прям по 2-3 задачки на каждый алгоритм для закрепления
Алгоритмы и структуры данных уже начали - вот бинарный поиск первое из видео серии. В плейлисте с задачками - как раз сейчас задачи на бинарный поиск. Дальше будет много всего интересного.
Даешь алгоритм обхода бинарного дерева в глубину/ширину? или инвертирования того же дерева)! Кто за, ставим лайки!
Хорошая идея! До этого тоже дойдем. Но вначале прийдется разобраться с деревьями и бинарными деревьями в частности.
@@frontendscience 6 месяц как ждем!
@@user-ju3sl1yx9e и в течение этих 6 месяцев для Вас лично прям ничего другого полезного не вышло на канале - вот сидите и ждете у компа все полгода.... грустненько.
Спасибо за видео👍
Алгоритм быстрой сортировки хотелось бы увидеть)
Благодарю за фибдек.
Отличный выбор :) запишем!
Спасибо за видео! По поводу поиска среднего элемента. Долго думал, почему надо прибавлять позицию левого указателя. Потом понял, что (right - left) / 2 + left == (right + left) / 2, то есть старое доброе среднее арифметическое двух чисел. По-моему, со средним арифметическим гораздо проще понять
Хотелось бы больше о самих алгоритмах, поняв алгоритм, лучше самому их реализовывать). Спасибо. Вот приятный канал!)
Нажал лайк, колокольчик на все уведомления!
Обожаю Ваш контент! Отличный материал! Спасибо за Ваш труд!
Очень приятно! Спасибо большое за поддержку! Это очень вдохновляет 😊🤩
классный видос, теперь буду знать как называется то что я применял )) спасибо
респект за имена с теории большого взрыва 😊
Спасибо за контент на вашем канале! Полезно!)
Благодарим за поддержку! Рады, что было полезно!
Блин, наверное первый раз с такой легкостью на сердце ставлю лайки в Ютубе под каждым просмотренным видосе на канале. Спасибо!
Круто! Очень приятно) благодарю за поддержку)
Спасибо большое!
Большое спасибо!
Лайк за Теорию Большого Взрыва)
Огромное спасибо! Очень ясно понятно, и самое главное видео не большое.
Отлично!
Огромное спасибо
Сергей, спасибо громадное! В отличие от Владилена вы обучаете вглубь, а не тому как бы быстрее начать писать код и начать зарабатывать. Продолжайте в том же духе. Очень нужно и ценно.
Ценю Вашу поддержку! :) Я тоже за то, чтоб начинать писать код пораньше и получать опыт. Но в то же время наращивать глубину знаний. Потому что благодаря им будет качественное развитие как профессионала.
Спасибо огромное! Не думал, что за 6 минут можно легко выучить бинарный поиск. Я сначала середины рассчитывал как (right+left)/2 - но из-за этого получалось на 1 итерацию больше. Упростил ваше выражение, получилось right-3*left;
Чтобы уменьшить итерации сделай проверку, arr[left] или arr[right] === target.
function binarySearch(array: any, target: any) {
if (!Array.isArray(array)) {
return -1;
}
let left = 0;
let right = array.length;
while (left
Отличное видео! Было бы интересно увидеть бинарный поиск по дереву)
Как до деревьев дойдем - будет!
Интересно было бы послушать про поиск при помощи регулярных выражений
шикарное видео, алгоритмы- это то, что нужно любому разработчику
Благодарим за поддержку. Дальше будет еще много полезного! Stay tuned
Доступнее, чем в книгах.
Наверное вся жизнь построена на бинарном поиске (как говорится: вселенная стремится к балансу ) где left и right - крайности а mid - это то самый баланс) Нам хорошо когда ми в этом балансе. Если в духовном плане (баланс) это спокойствие. Спокойствие это когда мы не слишком угрюмые и не слишком эмоциональные(например что бы уснуть нам нужно спокойствие- мы не уснем когда будем слишком радостные или наоборот переживать за что то) Если в лечении болезни например то лекарство от яда отличается дозой. Если его мало(left) - нет смыла, если много(right) - вред для организма и тут нам нужен 3-й указатель - mid, также можно наводить еще много примеров где бинарный поиск будет актуальным) спасибо что дочитали это до конца)) Хотя у меня куча крутых каналов в подписках но Ваш в топе)
Интересная аналогия)
Где то я уже это слышал) cs50
Решал задачу на поиск из входного массива элемента, у которого индекс совпадает собственно, с самим числом. Банальная невнимательность не позволяла до конца понять, почему данный алгоритм так работает, если учесть, что задача требовала пройти тест на производительность. Конечно, решение всё-таки удалось отыскать, хоть и с применением рекурсии... Спустя 10-ки попыток, снова пересмотрел Ваше видео, всё встало на свои места. Ваш труд не останется в стороне. Браво и большое спасибо за объяснения!!
Благодарю, очень вдохновляет)
Красота. Пора учить алгоритмы)
Походу пора снимать новые видео)) Мотивируешь!
@@frontendscience буду только рад новым видео. Задачки всегда будут интересны) Ещё раз спасибо за твой труд
Как будто пересказ книги 1 главы Грокаем Алгоритмы. Полезно будет для новичков.
В книге описаны примеры на Python, а Сергей перевел их в JavaScript, спасибо! Хорошая работа.
Прикольно! Это что мне пора книгу писать?)
@@frontendscience я бы посоветовал)
какая разница для какого языка примеры, когда математика одна для всех в мире
Очень полезный материал. Так бы все по одному алгоритму разобрать. Быстро и доходчиво
Рад, что понравилось! Да, такое есть в планах.)
Благодарю
спасибо большое, разобрался
Спасибо за видео. Я скидывал задачу на почту, хотелось бы её разбор увидеть:)
Рад что понравилось. Задача отличная! Хороший повод записать видео про каррирование! :)
Вот только сегодня реализовал это метод на JavaScript. Как же удивительно устроен мир). Я ведь даже не гуглил, из книги взял алгоритм. Я иначе реализовал, более 'математически').
Добрый день ! Запишите плз еще ответы на вопросы для Middle and Senior и как надо правильно на них отвечать. Вот варианты с Доу : 44.У чому принципова різниця між подіями mouseleave і mouseout?
45.У якому порядку обробляються призначені для користувача події в DOM (click, mouseover тощо)? FIFO чи LIFO?
46.Що таке Event bubbling та Event capturing?
47.Порівняйте методи об’єкта event stopPropagation та stopImmediateProparation.
48.Які є підходи оптимізації продуктивності вебсторінки?
49.Як реалізований механізм same-origin policy в браузері? На які браузерні API він поширюється?
50.Назвіть способи зберігання даних у браузері. Порівняйте їх.
51.Web worker’и. Опишіть особливості передачі даних між worker’ами та основним потоком, між розділеними worker’ами.
51.Що таке Transferable-об’єкти?
52.Розкажіть про способи оптимізації виконання ресурсомістких операцій JS для поліпшення продуктивності рендерингу контенту на сторінці.
53.Чому ResizeObserver викликає події зміни розміру до відтворення елемента, а не після?
54.Розкажіть, як ви розумієте Web Accessibility?
55.Опишіть алгоритм створення функціоналу, що забезпечує читання вмісту .txt-файлу при перетягуванні його з файлової системи у вікно браузера.
56.Що таке Virtual DOM? Спасибо ! Особенно интересно про производительность в вебе - уж очень часто спрашивают
Такое тоже есть в планах :) но чуть позже.
Прикольно. Оказывается я знал этот алгоритм всю свою жизнь из прикола "как поймать льва в пустыне".
Найс! Надо посмотреть, что это за прикол "поймать льва в пустыне")
Очень надеюсь, что продолжение будет
Готовится :)
Сортировку, которая сочетает простоту в понимании и с адекватной сложностью алгоритма по времени и памяти.
4:23 Интересное вычисление среднего элемента...
mid = Math.floor((min + max) / 2); // 1 вариант
mid = ~~((min + max) / 2); // 2 вариант
я использую побитовое НЕ, так короче
mid = (min + max) >> 1
было бы круто взять массив отсортированных данных, и показать разницу по времени. Или сделать небольшой курс уроков что бы было понятно где что использовать, бинарный поиск или другой вид
У нас планируется видео про сложность алгоритмов (Big O). Там как раз разберем разницу по времени исполнения различных алгоритмов на разных примерах. Stay tuned.
Посмотрел недели три назад, сегодня буду внедрять.
Класс! Клево, что пригодилось!
middlle = Math.floor(start(left) + end(right) /2 )
с минусом как на видео делают для защиты от оверфлоу
Нужно собрать мегаминкс)
т.е если придется сначала сортировать массив, и только потом что-то искать внутри, то все равно сложность будет выше, чем если бы мы просто сразу использовали метод массива?
можно отсортировать 1 раз и потом много раз быстро искать.
Все по очереди
то если использовать метод фильтр массива это линейная сложность выходит, для поиска элемента? и другой вопрос если искать по строкам в массиве, нужно сделать отсортировку?
Да. И да.
Дякую
Ахах, как видите все очень просто. 😀
сделайте обзор , как сделать функцию бомба ,например чтобы через какой то промежуток времени слово самоуничтожалось и будет интересно что б был звук взрыва
Добрый день!
Во-первых, спасибо за простой и понятный разбор.
Второй момент, хочу попробовать интегрировать этот алгоритм в мини-игру "Угадай число" (да-да, всем известная игра для начинающих 😉), но хочу, чтоб отгадывал компьютер. Меня смущает только один момент - не могу придумать, как реализовать подсказку "больше-меньше" и соответствующие шаги. буду благодарен за совет.
P.s. если все же сам смогу решить, напишу код сюда.
Еще раз спасибо!
смотри компьютер всегда будет делить доступный range на 2 и говорить пользователю середину. а пользователь говорит больше или меньше. У нас в коде это были if() в которых мы сравнивали с target. тут тебе надо давать пользователю выбрать и его ответ подставить в if
@@frontendscience да, это понятно, что if решает. Но, я когда пытался сделать это, он получался многоэтажный, что не есть хорошо.
В итоге я сделал чуть иначе, подсмотрев идею в другом проекте. Там на кнопки ставили обработчик события, и в зависимости от нажатой кнопки сдвигали верхний и нижний пределы.
Отличная идея
@@frontendscience спасибо. Но, увы, в целом она не моя.
Я только применил ее в своей ситуации
@@stastikhomirov8075 ну не всегда надо велосипед изобретать! Успехов
Спасибо за видео!
только не совсем понимаю зачем усложнять когда можно просто воспользоваться методом arr.indexOf(serchElem) ?
но при нестандартных ситуациях наверное необходимо знать такие алгоритмы - существенно сократят время и ресурсы машины.
кстати, возник логичный вопрос - какой метод поиска использует метод arr.indexOf(serchElem) , линейный или бинарный?
Проверил, алгоритм array.indexOf(searchElem) проигрывает 15 секунд бинарному алгоритму поиска при 10млн. элементах в массиве для поиска.
Сергей, а можно этот алгоритм использовать для строчных типов данных?
У строк есть свой метод indexOf.
IndexOf у массивов линейный, так как для бинарного поиска нужна сортировка а indexOf работает для любого порядка элементов
Интересует, как объяснять алгоритм индекса на основе бинарных деревьев.?
Когда-нибудь мы до них дойдем)
Интересно то, что для маленьких массивов indexOf() работает быстрее чем бинарный поиск:
console.time('binary')
search(array, 9)
console.timeEnd('binary')
binary: 0.02001953125ms
========================
console.time('indexOf')
array.indexOf(9)
console.timeEnd('indexOf')
indexOf: 0.010009765625ms
Чтобы данные были корректными нужно повторить расчёт несколько раз. Например, 10000 раз.
Не понял зачем ((right - left)/ 2) + left. Мы же ниже всё равно меняем позицию left, нет?
Нормальные люди махом вычисляют средний индекс: (right+left)/2. Автор почему-то решил отдельно вычислять полудлину диапазона поиска, а потом отдельно добавлять смещение левого края, чтобы найти в итоге тот же средний индекс. По математике выражения эквивалентны, так что всё нормально. Только компьютеру лишние действия, но когда фронтендщики переживали на этот счет :-)
@@alexuspro26 В решение ((right - left)/ 2) + left используется более маленькие числа, и из этого следует, что нужно меньше памяти.
@@surensamarchyan7230 JS любое число хранит в 64 битах. Числа 34 и 7346752 занимают одинаковое количество памяти. Если же Вы собираетесь хранить и обсчитывать строки, но думаете о битах, то подумайте о тактах. В общем, не убедили.
а почему если определить значение mid сразу при объявлении переменной - код не работает?
Потому что при следующем цикле mid должен обновиться исходя их новых значений right и left.
@@nicealx спасибо
Хммм, я бы заменил 9 строку на mid = Math.round((left + right)/2); Тут будет меньше текста, а работает аналогично.
Разрешаю )
в моём счастливом советском детстве этот метод назывался просто: "метод деления пополам"... 😝
Тут косяк, при 1 млн, нужно не млн итераций, если делать обычным перебором O(n) и если искомая фамилия последняя, достаточно 1млн-1, следовательно с 2млн соответственно
pied piper ☺
Простите за глупый вопрос. Я не понимаю, зачем в мид надо приплюсовывать лефт?
У випадку, якщо шуканий елемент буде правіше середини, після переприсвоювання лефт в наступному циклі середину буде знайдено неправильно, тобто вона буде менша за лефт.
@@_vasyl_5039 дякую))
В случае, если искомый элемент будет правее середины, после переприсваивания лет в следующем цикле середина будет найдена неправильно, то есть она будет меньше лефт.
1:54
а как насчет того случая, когда у нас искомый элемент в массиве не один? можно усугубить - ненужные тоже, по крайней мере, несколько. в телефонной книге, с которой Вы начали, будет, именно, так. или интервьюеры этого, почти наверняка, не понимают. кстати, это еще и по поводу популярной сентенции, что математика и образование для программиста не обязательны. и еще. бинарный поиск - это лучше чем перебор, но это не оптимальный алгоритм.
Кейс когда есть повторы - тоже не проблема. Сортируем. С помощью бинарного поиска ищем любой из дубликатов. потом двумя указателями расходимся влево и вправо - находим границы всех повторов.
А какой по вашему мнению будет самы оптимальный вариант поиска в таком случае?
Добрый день, подскажите пожалуйста в какой программе работали в этом видео?
В смысле, в какой программе создавал видео?
@@frontendscience Извиняюсь за неточный вопрос, в чём написать такой алгоритм, чтобы его можно было запустить?
Я часто использую сайт codepen для этого
@@frontendscience Спасибо!
из какого мультика улитка на 1 30?
«Университет монстров».
Красно черные деревья))
Не уверен, что такое спросят на фронтенд разработчика - скорее это фулстэк или бэкенд. Но я подумаю. Благодарю)
А можно еще попросить о python рассказать?
Извините, я по Js.
@@frontendscience хорошо. Спасибо, js мне тоже нужен. У вас самое понятное объяснение.
Js и python похожи. Ты просто можешь адаптировать этот код под синтаксис python. Насколько знаю нужно просто по-другому массив назначить и убрать фигурные скобки
че за имена? Шелдон Пени? это на сорта яблок больше похоже
Алгоритм перестановки без повторений. Пример число 5 = 0000012345
бинарный поиск это поиск строго по очереди от 0 до 100 допистим или может быть 25,14,15,3...????
тільки для відсортованих масивів
Сказали же, строго отсортированный массив.
А если массив не отсортированный?
Тогда бинарным поиском не получится решить.
@@frontendscience Если выпадет на mid или искомый элемент справа отсортирован, то получится : )
не проще L + R / 2 ?
Число может оказаться не целым
@@kalts_daniil Math.floor((l + r)/2)
Да но массив данных должен быть отсортированным.
Да должен быть!
@@frontendscience сортируем пущырьком и получаем O(n2) :D
((right - left)/ 2) + left. С какой целью left прибавляем в конце ?
я просто прописываю Math.floor((right+left)/2) и все работает!! и в let right = array.length (без -1). Может как-то влияет, конечно, но работает)
Чтобы в случае, если левый и правый указатели одновременно указывали на искомое число программа не уходила в бесконечный цикл
left прибавляется, чтобы сдвинуть область поиска к начальной точки left.
Т.е., если у тебя left 50, а right 100, то (100-50)/2 = 25, а нам нужна область с 50 до 100.
Прибавляя к 25 50, получаем 75, что является искомой серединой отрезка left 50 - right 100.
Чисто математически ((right - left)/ 2) + left это то же самое, что и (right + left)/ 2
Но в программировании есть свои ньюансы, поэтому лучше употреблять первое выражение. можно конечно употребить второе, но только если Вы точно уверены, что оно сработает правильно. А оно не всегда может сработать правильно, ибо есть такая штука как переполнение.