Binary Search Algorithm | JavaScript

[@vladsosnov3749]

Спасибо за видео👍 Алгоритм быстрой сортировки хотелось бы увидеть)

[@frontendscience]

Благодарю за фибдек. Отличный выбор :) запишем!

[@mrivanan101]

Спасибо за видео! По поводу поиска среднего элемента. Долго думал, почему надо прибавлять позицию левого указателя. Потом понял, что (right - left) / 2 + left == (right + left) / 2, то есть старое доброе среднее арифметическое двух чисел. По-моему, со средним арифметическим гораздо проще понять

[@alexr6829]

Даешь алгоритм обхода бинарного дерева в глубину/ширину? или инвертирования того же дерева)! Кто за, ставим лайки!

[@frontendscience]

Хорошая идея! До этого тоже дойдем. Но вначале прийдется разобраться с деревьями и бинарными деревьями в частности.

[@ПавелМельничук-с4ш]

@@frontendscience 6 месяц как ждем!

[@frontendscience]

@@ПавелМельничук-с4ш и в течение этих 6 месяцев для Вас лично прям ничего другого полезного не вышло на канале - вот сидите и ждете у компа все полгода.... грустненько.

[@denisoleksyuk5346]

Я бы хотел разобрать все самые известные алгоритмы, можно прям с книги грокаем алгоритмы, там и про графы, Дейкстры и т.д, можно было бы прям по 2-3 задачки на каждый алгоритм для закрепления

[@frontendscience]

Алгоритмы и структуры данных уже начали - вот бинарный поиск первое из видео серии. В плейлисте с задачками - как раз сейчас задачи на бинарный поиск. Дальше будет много всего интересного.

[@valeriivolkov_ua]

Блин, наверное первый раз с такой легкостью на сердце ставлю лайки в Ютубе под каждым просмотренным видосе на канале. Спасибо!

[@frontendscience]

Круто! Очень приятно) благодарю за поддержку)

[@timoshagoogle5678]

шикарное видео, алгоритмы- это то, что нужно любому разработчику

[@frontendscience]

Благодарим за поддержку. Дальше будет еще много полезного! Stay tuned

[@olehy5000]

Обожаю Ваш контент! Отличный материал! Спасибо за Ваш труд!

[@frontendscience]

Очень приятно! Спасибо большое за поддержку! Это очень вдохновляет 😊🤩

[@sergeiosokin300]

Спасибо за контент на вашем канале! Полезно!)

[@frontendscience]

Благодарим за поддержку! Рады, что было полезно!

[@ДмитрийЩ-у7д]

Сергей, спасибо громадное! В отличие от Владилена вы обучаете вглубь, а не тому как бы быстрее начать писать код и начать зарабатывать. Продолжайте в том же духе. Очень нужно и ценно.

[@frontendscience]

Ценю Вашу поддержку! :) Я тоже за то, чтоб начинать писать код пораньше и получать опыт. Но в то же время наращивать глубину знаний. Потому что благодаря им будет качественное развитие как профессионала.

[@sayko003]

Как будто пересказ книги 1 главы Грокаем Алгоритмы. Полезно будет для новичков. В книге описаны примеры на Python, а Сергей перевел их в JavaScript, спасибо! Хорошая работа.

[@frontendscience]

Прикольно! Это что мне пора книгу писать?)

[@mikagasparyan5029]

@@frontendscience я бы посоветовал)

[@rq9kd]

какая разница для какого языка примеры, когда математика одна для всех в мире

[@multiply87]

Красота. Пора учить алгоритмы)

[@frontendscience]

Походу пора снимать новые видео)) Мотивируешь!

[@multiply87]

@@frontendscience буду только рад новым видео. Задачки всегда будут интересны) Ещё раз спасибо за твой труд

[@GSySte]

Решал задачу на поиск из входного массива элемента, у которого индекс совпадает собственно, с самим числом. Банальная невнимательность не позволяла до конца понять, почему данный алгоритм так работает, если учесть, что задача требовала пройти тест на производительность. Конечно, решение всё-таки удалось отыскать, хоть и с применением рекурсии... Спустя 10-ки попыток, снова пересмотрел Ваше видео, всё встало на свои места. Ваш труд не останется в стороне. Браво и большое спасибо за объяснения!!

[@frontendscience]

Благодарю, очень вдохновляет)

[@JavaScript_00]

Огромное спасибо! Очень ясно понятно, и самое главное видео не большое.

[@soloviyshpak]

респект за имена с теории большого взрыва 😊

[@РоманГирич-з5ш]

классный видос, теперь буду знать как называется то что я применял )) спасибо

[@АлександрШевченко-б1я9з]

Отличное видео! Было бы интересно увидеть бинарный поиск по дереву)

[@frontendscience]

Как до деревьев дойдем - будет!

[@userman6193]

Хотелось бы больше о самих алгоритмах, поняв алгоритм, лучше самому их реализовывать). Спасибо. Вот приятный канал!)

[@colemanphonecolemanphone3387]

Очень полезный материал. Так бы все по одному алгоритму разобрать. Быстро и доходчиво

[@frontendscience]

Рад, что понравилось! Да, такое есть в планах.)

[@suginikaiasarux]

Лайк за Теорию Большого Взрыва)

[@ІльченкоАртем]

Наверное вся жизнь построена на бинарном поиске (как говорится: вселенная стремится к балансу ) где left и right - крайности а mid - это то самый баланс) Нам хорошо когда ми в этом балансе. Если в духовном плане (баланс) это спокойствие. Спокойствие это когда мы не слишком угрюмые и не слишком эмоциональные(например что бы уснуть нам нужно спокойствие- мы не уснем когда будем слишком радостные или наоборот переживать за что то) Если в лечении болезни например то лекарство от яда отличается дозой. Если его мало(left) - нет смыла, если много(right) - вред для организма и тут нам нужен 3-й указатель - mid, также можно наводить еще много примеров где бинарный поиск будет актуальным) спасибо что дочитали это до конца)) Хотя у меня куча крутых каналов в подписках но Ваш в топе)

[@frontendscience]

Интересная аналогия)

[@АртемВ-ш7щ]

Доступнее, чем в книгах.

[@-anonim-3008]

Спасибо огромное! Не думал, что за 6 минут можно легко выучить бинарный поиск. Я сначала середины рассчитывал как (right+left)/2 - но из-за этого получалось на 1 итерацию больше. Упростил ваше выражение, получилось right-3*left;

[@ПетрПетров-ж9е]

Чтобы уменьшить итерации сделай проверку, 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

[@cardinalerror1]

Нажал лайк, колокольчик на все уведомления!

[@maksimmnatsakanov2853]

Спасибо за видео. Я скидывал задачу на почту, хотелось бы её разбор увидеть:)

[@frontendscience]

Рад что понравилось. Задача отличная! Хороший повод записать видео про каррирование! :)

[@andrewb3790]

Добрый день ! Запишите плз еще ответы на вопросы для 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? Спасибо ! Особенно интересно про производительность в вебе - уж очень часто спрашивают

[@frontendscience]

Такое тоже есть в планах :) но чуть позже.

[@oxanananieva2643]

Очень надеюсь, что продолжение будет

[@frontendscience]

Готовится :)

[@tenobi1]

Интересно было бы послушать про поиск при помощи регулярных выражений

[@Anopeng]

4:23 Интересное вычисление среднего элемента... mid = Math.floor((min + max) / 2); // 1 вариант mid = ~~((min + max) / 2); // 2 вариант

[@rq9kd]

я использую побитовое НЕ, так короче

[@alexuspro26]

mid = (min + max) >> 1

[@Chambo015]

Где то я уже это слышал) cs50

[@moguha]

Огромное спасибо

[@anazkomult]

Прикольно. Оказывается я знал этот алгоритм всю свою жизнь из прикола "как поймать льва в пустыне".

[@frontendscience]

Найс! Надо посмотреть, что это за прикол "поймать льва в пустыне")

[@userman6193]

Вот только сегодня реализовал это метод на JavaScript. Как же удивительно устроен мир). Я ведь даже не гуглил, из книги взял алгоритм. Я иначе реализовал, более 'математически').

[@vitaliivoitovych5851]

Отлично!

[@atli4nikk160]

Сортировку, которая сочетает простоту в понимании и с адекватной сложностью алгоритма по времени и памяти.

[@NoName-zh7cc]

Спасибо большое!

[@dmytrokoka3796]

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

[@frontendscience]

У нас планируется видео про сложность алгоритмов (Big O). Там как раз разберем разницу по времени исполнения различных алгоритмов на разных примерах. Stay tuned.

[@someoneiniiaks9837]

Посмотрел недели три назад, сегодня буду внедрять.

[@frontendscience]

Класс! Клево, что пригодилось!

[@alenachuyankova]

Большое спасибо!

[@isaabk4409]

Спасибо!

[@deanwichester6412]

middlle = Math.floor(start(left) + end(right) /2 )

[@dmitriikorotkin]

с минусом как на видео делают для защиты от оверфлоу

[@Axe11er]

т.е если придется сначала сортировать массив, и только потом что-то искать внутри, то все равно сложность будет выше, чем если бы мы просто сразу использовали метод массива?

[@silentage6310]

можно отсортировать 1 раз и потом много раз быстро искать.

[@АртемТимофеев-я1ы]

спасибо большое, разобрался

[@stastikhomirov8075]

Добрый день! Во-первых, спасибо за простой и понятный разбор. Второй момент, хочу попробовать интегрировать этот алгоритм в мини-игру "Угадай число" (да-да, всем известная игра для начинающих 😉), но хочу, чтоб отгадывал компьютер. Меня смущает только один момент - не могу придумать, как реализовать подсказку "больше-меньше" и соответствующие шаги. буду благодарен за совет. P.s. если все же сам смогу решить, напишу код сюда. Еще раз спасибо!

[@frontendscience]

смотри компьютер всегда будет делить доступный range на 2 и говорить пользователю середину. а пользователь говорит больше или меньше. У нас в коде это были if() в которых мы сравнивали с target. тут тебе надо давать пользователю выбрать и его ответ подставить в if

[@stastikhomirov8075]

@@frontendscience да, это понятно, что if решает. Но, я когда пытался сделать это, он получался многоэтажный, что не есть хорошо. В итоге я сделал чуть иначе, подсмотрев идею в другом проекте. Там на кнопки ставили обработчик события, и в зависимости от нажатой кнопки сдвигали верхний и нижний пределы.

[@frontendscience]

Отличная идея

[@stastikhomirov8075]

@@frontendscience спасибо. Но, увы, в целом она не моя. Я только применил ее в своей ситуации

[@frontendscience]

@@stastikhomirov8075 ну не всегда надо велосипед изобретать! Успехов

[@Сома-р2х]

то если использовать метод фильтр массива это линейная сложность выходит, для поиска элемента? и другой вопрос если искать по строкам в массиве, нужно сделать отсортировку?

[@frontendscience]

Да. И да.

[@fl1mo47]

Благодарю

[@MsLodir]

Все по очереди

[@alenachuyankova]

Простите за глупый вопрос. Я не понимаю, зачем в мид надо приплюсовывать лефт?

[@_vasyl_5039]

У випадку, якщо шуканий елемент буде правіше середини, після переприсвоювання лефт в наступному циклі середину буде знайдено неправильно, тобто вона буде менша за лефт.

[@dimondsafkage4620]

@@_vasyl_5039 дякую))

[@АртемВ-ш7щ]

В случае, если искомый элемент будет правее середины, после переприсваивания лет в следующем цикле середина будет найдена неправильно, то есть она будет меньше лефт.

[@ПетрПетров-ж9е]

1:54

[@kreamzfy]

а почему если определить значение mid сразу при объявлении переменной - код не работает?

[@nicealx]

Потому что при следующем цикле mid должен обновиться исходя их новых значений right и left.

[@kreamzfy]

@@nicealx спасибо

[@romikonlinepotapenko3475]

Интересно то, что для маленьких массивов 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

[@ИмяФамилия-э4ф7в]

Чтобы данные были корректными нужно повторить расчёт несколько раз. Например, 10000 раз.

[@no1imwr43]

Не понял зачем ((right - left)/ 2) + left. Мы же ниже всё равно меняем позицию left, нет?

[@alexuspro26]

Нормальные люди махом вычисляют средний индекс: (right+left)/2. Автор почему-то решил отдельно вычислять полудлину диапазона поиска, а потом отдельно добавлять смещение левого края, чтобы найти в итоге тот же средний индекс. По математике выражения эквивалентны, так что всё нормально. Только компьютеру лишние действия, но когда фронтендщики переживали на этот счет :-)

[@surensamarchyan7230]

​@@alexuspro26 В решение ((right - left)/ 2) + left используется более маленькие числа, и из этого следует, что нужно меньше памяти.

[@alexuspro26]

@@surensamarchyan7230 JS любое число хранит в 64 битах. Числа 34 и 7346752 занимают одинаковое количество памяти. Если же Вы собираетесь хранить и обсчитывать строки, но думаете о битах, то подумайте о тактах. В общем, не убедили.

[@АлександрСавченко-б8в]

из какого мультика улитка на 1 30?

[@frontendscience]

«Университет монстров».

[@СергейКрагель-ъ6г]

Добрый день, подскажите пожалуйста в какой программе работали в этом видео?

[@frontendscience]

В смысле, в какой программе создавал видео?

[@СергейКрагель-ъ6г]

@@frontendscience Извиняюсь за неточный вопрос, в чём написать такой алгоритм, чтобы его можно было запустить?

[@frontendscience]

Я часто использую сайт codepen для этого

[@СергейКрагель-ъ6г]

@@frontendscience Спасибо!

[@ВоинственныйХомяк-к8р]

Спасибо за видео! только не совсем понимаю зачем усложнять когда можно просто воспользоваться методом arr.indexOf(serchElem) ? но при нестандартных ситуациях наверное необходимо знать такие алгоритмы - существенно сократят время и ресурсы машины. кстати, возник логичный вопрос - какой метод поиска использует метод arr.indexOf(serchElem) , линейный или бинарный?

[@ВоинственныйХомяк-к8р]

Проверил, алгоритм array.indexOf(searchElem) проигрывает 15 секунд бинарному алгоритму поиска при 10млн. элементах в массиве для поиска. Сергей, а можно этот алгоритм использовать для строчных типов данных?

[@frontendscience]

У строк есть свой метод indexOf.

[@frontendscience]

IndexOf у массивов линейный, так как для бинарного поиска нужна сортировка а indexOf работает для любого порядка элементов

[@shanthakobyan3578]

сделайте обзор , как сделать функцию бомба ,например чтобы через какой то промежуток времени слово самоуничтожалось и будет интересно что б был звук взрыва

[@СашаТрисектор]

а как насчет того случая, когда у нас искомый элемент в массиве не один? можно усугубить - ненужные тоже, по крайней мере, несколько. в телефонной книге, с которой Вы начали, будет, именно, так. или интервьюеры этого, почти наверняка, не понимают. кстати, это еще и по поводу популярной сентенции, что математика и образование для программиста не обязательны. и еще. бинарный поиск - это лучше чем перебор, но это не оптимальный алгоритм.

[@frontendscience]

Кейс когда есть повторы - тоже не проблема. Сортируем. С помощью бинарного поиска ищем любой из дубликатов. потом двумя указателями расходимся влево и вправо - находим границы всех повторов. А какой по вашему мнению будет самы оптимальный вариант поиска в таком случае?

[@cardinalerror1]

Интересует, как объяснять алгоритм индекса на основе бинарных деревьев.?

[@frontendscience]

Когда-нибудь мы до них дойдем)

[@alexrybalov8917]

Хммм, я бы заменил 9 строку на mid = Math.round((left + right)/2); Тут будет меньше текста, а работает аналогично.

[@frontendscience]

Разрешаю )

[@Константин-в6ш5ж]

Красно черные деревья))

[@frontendscience]

Не уверен, что такое спросят на фронтенд разработчика - скорее это фулстэк или бэкенд. Но я подумаю. Благодарю)

[@romanenkosergio]

Нужно собрать мегаминкс)

[@dimaborovik7857]

Тут косяк, при 1 млн, нужно не млн итераций, если делать обычным перебором O(n) и если искомая фамилия последняя, достаточно 1млн-1, следовательно с 2млн соответственно

[@mityaaleks4214]

А если массив не отсортированный?

[@frontendscience]

Тогда бинарным поиском не получится решить.

[@im_dmitriy]

@@frontendscience Если выпадет на mid или искомый элемент справа отсортирован, то получится : )

[@dnk_777]

А можно еще попросить о python рассказать?

[@frontendscience]

Извините, я по Js.

[@dnk_777]

@@frontendscience хорошо. Спасибо, js мне тоже нужен. У вас самое понятное объяснение.

[@FrontendPlace]

Js и python похожи. Ты просто можешь адаптировать этот код под синтаксис python. Насколько знаю нужно просто по-другому массив назначить и убрать фигурные скобки

[@domikpriklyocheniu3611]

бинарный поиск это поиск строго по очереди от 0 до 100 допистим или может быть 25,14,15,3...????

[@yundon8182]

Сказали же, строго отсортированный массив.

[@serj0peleng]

в моём счастливом советском детстве этот метод назывался просто: "метод деления пополам"... 😝

[@wisarty]

Дякую

[@ihorkowalski3013]

не проще L + R / 2 ?

[@kalts_daniil]

Число может оказаться не целым

[@webbrother]

@@kalts_daniil Math.floor((l + r)/2)

[@СергейБердюгин-ь7ф]

pied piper ☺

[@evgendrapkin7111]

Да но массив данных должен быть отсортированным.

[@frontendscience]

Да должен быть!

[@Antonym-b5o]

@@frontendscience сортируем пущырьком и получаем O(n2) :D

[@DerAleksey]

че за имена? Шелдон Пени? это на сорта яблок больше похоже

[@blackgolddev4023]

Алгоритм перестановки без повторений. Пример число 5 = 0000012345

[@grintea4163]

Ахах, как видите все очень просто. 😀

[@evgeniy3370]

((right - left)/ 2) + left. С какой целью left прибавляем в конце ?

[@LenaFelica_songwriter]

я просто прописываю Math.floor((right+left)/2) и все работает!! и в let right = array.length (без -1). Может как-то влияет, конечно, но работает)

[@RENOMIZER]

Чтобы в случае, если левый и правый указатели одновременно указывали на искомое число программа не уходила в бесконечный цикл

[@plan-4D]

left прибавляется, чтобы сдвинуть область поиска к начальной точки left. Т.е., если у тебя left 50, а right 100, то (100-50)/2 = 25, а нам нужна область с 50 до 100. Прибавляя к 25 50, получаем 75, что является искомой серединой отрезка left 50 - right 100.

[@glukmaker]

Чисто математически ((right - left)/ 2) + left это то же самое, что и (right + left)/ 2 Но в программировании есть свои ньюансы, поэтому лучше употреблять первое выражение. можно конечно употребить второе, но только если Вы точно уверены, что оно сработает правильно. А оно не всегда может сработать правильно, ибо есть такая штука как переполнение.