Я бы хотел разобрать все самые известные алгоритмы, можно прям с книги грокаем алгоритмы, там и про графы, Дейкстры и т.д, можно было бы прям по 2-3 задачки на каждый алгоритм для закрепления
Алгоритмы и структуры данных уже начали - вот бинарный поиск первое из видео серии. В плейлисте с задачками - как раз сейчас задачи на бинарный поиск. Дальше будет много всего интересного.
Спасибо за видео! По поводу поиска среднего элемента. Долго думал, почему надо прибавлять позицию левого указателя. Потом понял, что (right - left) / 2 + left == (right + left) / 2, то есть старое доброе среднее арифметическое двух чисел. По-моему, со средним арифметическим гораздо проще понять
@@ПавелМельничук-с4ш и в течение этих 6 месяцев для Вас лично прям ничего другого полезного не вышло на канале - вот сидите и ждете у компа все полгода.... грустненько.
Решал задачу на поиск из входного массива элемента, у которого индекс совпадает собственно, с самим числом. Банальная невнимательность не позволяла до конца понять, почему данный алгоритм так работает, если учесть, что задача требовала пройти тест на производительность. Конечно, решение всё-таки удалось отыскать, хоть и с применением рекурсии... Спустя 10-ки попыток, снова пересмотрел Ваше видео, всё встало на свои места. Ваш труд не останется в стороне. Браво и большое спасибо за объяснения!!
Как будто пересказ книги 1 главы Грокаем Алгоритмы. Полезно будет для новичков. В книге описаны примеры на Python, а Сергей перевел их в JavaScript, спасибо! Хорошая работа.
Сергей, спасибо громадное! В отличие от Владилена вы обучаете вглубь, а не тому как бы быстрее начать писать код и начать зарабатывать. Продолжайте в том же духе. Очень нужно и ценно.
Ценю Вашу поддержку! :) Я тоже за то, чтоб начинать писать код пораньше и получать опыт. Но в то же время наращивать глубину знаний. Потому что благодаря им будет качественное развитие как профессионала.
Спасибо огромное! Не думал, что за 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
Добрый день ! Запишите плз еще ответы на вопросы для 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? Спасибо ! Особенно интересно про производительность в вебе - уж очень часто спрашивают
Наверное вся жизнь построена на бинарном поиске (как говорится: вселенная стремится к балансу ) где left и right - крайности а mid - это то самый баланс) Нам хорошо когда ми в этом балансе. Если в духовном плане (баланс) это спокойствие. Спокойствие это когда мы не слишком угрюмые и не слишком эмоциональные(например что бы уснуть нам нужно спокойствие- мы не уснем когда будем слишком радостные или наоборот переживать за что то) Если в лечении болезни например то лекарство от яда отличается дозой. Если его мало(left) - нет смыла, если много(right) - вред для организма и тут нам нужен 3-й указатель - mid, также можно наводить еще много примеров где бинарный поиск будет актуальным) спасибо что дочитали это до конца)) Хотя у меня куча крутых каналов в подписках но Ваш в топе)
было бы круто взять массив отсортированных данных, и показать разницу по времени. Или сделать небольшой курс уроков что бы было понятно где что использовать, бинарный поиск или другой вид
У нас планируется видео про сложность алгоритмов (Big O). Там как раз разберем разницу по времени исполнения различных алгоритмов на разных примерах. Stay tuned.
т.е если придется сначала сортировать массив, и только потом что-то искать внутри, то все равно сложность будет выше, чем если бы мы просто сразу использовали метод массива?
Вот только сегодня реализовал это метод на JavaScript. Как же удивительно устроен мир). Я ведь даже не гуглил, из книги взял алгоритм. Я иначе реализовал, более 'математически').
то если использовать метод фильтр массива это линейная сложность выходит, для поиска элемента? и другой вопрос если искать по строкам в массиве, нужно сделать отсортировку?
сделайте обзор , как сделать функцию бомба ,например чтобы через какой то промежуток времени слово самоуничтожалось и будет интересно что б был звук взрыва
Интересно то, что для маленьких массивов 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
Добрый день! Во-первых, спасибо за простой и понятный разбор. Второй момент, хочу попробовать интегрировать этот алгоритм в мини-игру "Угадай число" (да-да, всем известная игра для начинающих 😉), но хочу, чтоб отгадывал компьютер. Меня смущает только один момент - не могу придумать, как реализовать подсказку "больше-меньше" и соответствующие шаги. буду благодарен за совет. P.s. если все же сам смогу решить, напишу код сюда. Еще раз спасибо!
смотри компьютер всегда будет делить доступный range на 2 и говорить пользователю середину. а пользователь говорит больше или меньше. У нас в коде это были if() в которых мы сравнивали с target. тут тебе надо давать пользователю выбрать и его ответ подставить в if
@@frontendscience да, это понятно, что if решает. Но, я когда пытался сделать это, он получался многоэтажный, что не есть хорошо. В итоге я сделал чуть иначе, подсмотрев идею в другом проекте. Там на кнопки ставили обработчик события, и в зависимости от нажатой кнопки сдвигали верхний и нижний пределы.
Спасибо за видео! только не совсем понимаю зачем усложнять когда можно просто воспользоваться методом arr.indexOf(serchElem) ? но при нестандартных ситуациях наверное необходимо знать такие алгоритмы - существенно сократят время и ресурсы машины. кстати, возник логичный вопрос - какой метод поиска использует метод arr.indexOf(serchElem) , линейный или бинарный?
Проверил, алгоритм array.indexOf(searchElem) проигрывает 15 секунд бинарному алгоритму поиска при 10млн. элементах в массиве для поиска. Сергей, а можно этот алгоритм использовать для строчных типов данных?
Нормальные люди махом вычисляют средний индекс: (right+left)/2. Автор почему-то решил отдельно вычислять полудлину диапазона поиска, а потом отдельно добавлять смещение левого края, чтобы найти в итоге тот же средний индекс. По математике выражения эквивалентны, так что всё нормально. Только компьютеру лишние действия, но когда фронтендщики переживали на этот счет :-)
@@surensamarchyan7230 JS любое число хранит в 64 битах. Числа 34 и 7346752 занимают одинаковое количество памяти. Если же Вы собираетесь хранить и обсчитывать строки, но думаете о битах, то подумайте о тактах. В общем, не убедили.
У випадку, якщо шуканий елемент буде правіше середини, після переприсвоювання лефт в наступному циклі середину буде знайдено неправильно, тобто вона буде менша за лефт.
В случае, если искомый элемент будет правее середины, после переприсваивания лет в следующем цикле середина будет найдена неправильно, то есть она будет меньше лефт.
а как насчет того случая, когда у нас искомый элемент в массиве не один? можно усугубить - ненужные тоже, по крайней мере, несколько. в телефонной книге, с которой Вы начали, будет, именно, так. или интервьюеры этого, почти наверняка, не понимают. кстати, это еще и по поводу популярной сентенции, что математика и образование для программиста не обязательны. и еще. бинарный поиск - это лучше чем перебор, но это не оптимальный алгоритм.
Кейс когда есть повторы - тоже не проблема. Сортируем. С помощью бинарного поиска ищем любой из дубликатов. потом двумя указателями расходимся влево и вправо - находим границы всех повторов. А какой по вашему мнению будет самы оптимальный вариант поиска в таком случае?
Js и python похожи. Ты просто можешь адаптировать этот код под синтаксис python. Насколько знаю нужно просто по-другому массив назначить и убрать фигурные скобки
Тут косяк, при 1 млн, нужно не млн итераций, если делать обычным перебором O(n) и если искомая фамилия последняя, достаточно 1млн-1, следовательно с 2млн соответственно
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 Но в программировании есть свои ньюансы, поэтому лучше употреблять первое выражение. можно конечно употребить второе, но только если Вы точно уверены, что оно сработает правильно. А оно не всегда может сработать правильно, ибо есть такая штука как переполнение.
Спасибо за видео👍
Алгоритм быстрой сортировки хотелось бы увидеть)
Благодарю за фибдек.
Отличный выбор :) запишем!
Я бы хотел разобрать все самые известные алгоритмы, можно прям с книги грокаем алгоритмы, там и про графы, Дейкстры и т.д, можно было бы прям по 2-3 задачки на каждый алгоритм для закрепления
Алгоритмы и структуры данных уже начали - вот бинарный поиск первое из видео серии. В плейлисте с задачками - как раз сейчас задачи на бинарный поиск. Дальше будет много всего интересного.
Спасибо за видео! По поводу поиска среднего элемента. Долго думал, почему надо прибавлять позицию левого указателя. Потом понял, что (right - left) / 2 + left == (right + left) / 2, то есть старое доброе среднее арифметическое двух чисел. По-моему, со средним арифметическим гораздо проще понять
Даешь алгоритм обхода бинарного дерева в глубину/ширину? или инвертирования того же дерева)! Кто за, ставим лайки!
Хорошая идея! До этого тоже дойдем. Но вначале прийдется разобраться с деревьями и бинарными деревьями в частности.
@@frontendscience 6 месяц как ждем!
@@ПавелМельничук-с4ш и в течение этих 6 месяцев для Вас лично прям ничего другого полезного не вышло на канале - вот сидите и ждете у компа все полгода.... грустненько.
Блин, наверное первый раз с такой легкостью на сердце ставлю лайки в Ютубе под каждым просмотренным видосе на канале. Спасибо!
Круто! Очень приятно) благодарю за поддержку)
Решал задачу на поиск из входного массива элемента, у которого индекс совпадает собственно, с самим числом. Банальная невнимательность не позволяла до конца понять, почему данный алгоритм так работает, если учесть, что задача требовала пройти тест на производительность. Конечно, решение всё-таки удалось отыскать, хоть и с применением рекурсии... Спустя 10-ки попыток, снова пересмотрел Ваше видео, всё встало на свои места. Ваш труд не останется в стороне. Браво и большое спасибо за объяснения!!
Благодарю, очень вдохновляет)
Обожаю Ваш контент! Отличный материал! Спасибо за Ваш труд!
Очень приятно! Спасибо большое за поддержку! Это очень вдохновляет 😊🤩
Как будто пересказ книги 1 главы Грокаем Алгоритмы. Полезно будет для новичков.
В книге описаны примеры на Python, а Сергей перевел их в JavaScript, спасибо! Хорошая работа.
Прикольно! Это что мне пора книгу писать?)
@@frontendscience я бы посоветовал)
какая разница для какого языка примеры, когда математика одна для всех в мире
шикарное видео, алгоритмы- это то, что нужно любому разработчику
Благодарим за поддержку. Дальше будет еще много полезного! Stay tuned
Сергей, спасибо громадное! В отличие от Владилена вы обучаете вглубь, а не тому как бы быстрее начать писать код и начать зарабатывать. Продолжайте в том же духе. Очень нужно и ценно.
Ценю Вашу поддержку! :) Я тоже за то, чтоб начинать писать код пораньше и получать опыт. Но в то же время наращивать глубину знаний. Потому что благодаря им будет качественное развитие как профессионала.
Хотелось бы больше о самих алгоритмах, поняв алгоритм, лучше самому их реализовывать). Спасибо. Вот приятный канал!)
Красота. Пора учить алгоритмы)
Походу пора снимать новые видео)) Мотивируешь!
@@frontendscience буду только рад новым видео. Задачки всегда будут интересны) Ещё раз спасибо за твой труд
Спасибо за контент на вашем канале! Полезно!)
Благодарим за поддержку! Рады, что было полезно!
Отличное видео! Было бы интересно увидеть бинарный поиск по дереву)
Как до деревьев дойдем - будет!
респект за имена с теории большого взрыва 😊
Где то я уже это слышал) cs50
классный видос, теперь буду знать как называется то что я применял )) спасибо
Огромное спасибо! Очень ясно понятно, и самое главное видео не большое.
Очень полезный материал. Так бы все по одному алгоритму разобрать. Быстро и доходчиво
Рад, что понравилось! Да, такое есть в планах.)
Спасибо огромное! Не думал, что за 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
Добрый день ! Запишите плз еще ответы на вопросы для 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? Спасибо ! Особенно интересно про производительность в вебе - уж очень часто спрашивают
Такое тоже есть в планах :) но чуть позже.
Наверное вся жизнь построена на бинарном поиске (как говорится: вселенная стремится к балансу ) где left и right - крайности а mid - это то самый баланс) Нам хорошо когда ми в этом балансе. Если в духовном плане (баланс) это спокойствие. Спокойствие это когда мы не слишком угрюмые и не слишком эмоциональные(например что бы уснуть нам нужно спокойствие- мы не уснем когда будем слишком радостные или наоборот переживать за что то) Если в лечении болезни например то лекарство от яда отличается дозой. Если его мало(left) - нет смыла, если много(right) - вред для организма и тут нам нужен 3-й указатель - mid, также можно наводить еще много примеров где бинарный поиск будет актуальным) спасибо что дочитали это до конца)) Хотя у меня куча крутых каналов в подписках но Ваш в топе)
Интересная аналогия)
Прикольно. Оказывается я знал этот алгоритм всю свою жизнь из прикола "как поймать льва в пустыне".
Найс! Надо посмотреть, что это за прикол "поймать льва в пустыне")
Интересно было бы послушать про поиск при помощи регулярных выражений
4:23 Интересное вычисление среднего элемента...
mid = Math.floor((min + max) / 2); // 1 вариант
mid = ~~((min + max) / 2); // 2 вариант
я использую побитовое НЕ, так короче
mid = (min + max) >> 1
Спасибо за видео. Я скидывал задачу на почту, хотелось бы её разбор увидеть:)
Рад что понравилось. Задача отличная! Хороший повод записать видео про каррирование! :)
Нажал лайк, колокольчик на все уведомления!
Лайк за Теорию Большого Взрыва)
было бы круто взять массив отсортированных данных, и показать разницу по времени. Или сделать небольшой курс уроков что бы было понятно где что использовать, бинарный поиск или другой вид
У нас планируется видео про сложность алгоритмов (Big O). Там как раз разберем разницу по времени исполнения различных алгоритмов на разных примерах. Stay tuned.
Очень надеюсь, что продолжение будет
Готовится :)
Доступнее, чем в книгах.
Огромное спасибо
Сортировку, которая сочетает простоту в понимании и с адекватной сложностью алгоритма по времени и памяти.
Посмотрел недели три назад, сегодня буду внедрять.
Класс! Клево, что пригодилось!
т.е если придется сначала сортировать массив, и только потом что-то искать внутри, то все равно сложность будет выше, чем если бы мы просто сразу использовали метод массива?
можно отсортировать 1 раз и потом много раз быстро искать.
Спасибо большое!
Вот только сегодня реализовал это метод на JavaScript. Как же удивительно устроен мир). Я ведь даже не гуглил, из книги взял алгоритм. Я иначе реализовал, более 'математически').
Отлично!
Большое спасибо!
middlle = Math.floor(start(left) + end(right) /2 )
с минусом как на видео делают для защиты от оверфлоу
то если использовать метод фильтр массива это линейная сложность выходит, для поиска элемента? и другой вопрос если искать по строкам в массиве, нужно сделать отсортировку?
Да. И да.
спасибо большое, разобрался
сделайте обзор , как сделать функцию бомба ,например чтобы через какой то промежуток времени слово самоуничтожалось и будет интересно что б был звук взрыва
Спасибо!
Интересно то, что для маленьких массивов 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 раз.
Добрый день!
Во-первых, спасибо за простой и понятный разбор.
Второй момент, хочу попробовать интегрировать этот алгоритм в мини-игру "Угадай число" (да-да, всем известная игра для начинающих 😉), но хочу, чтоб отгадывал компьютер. Меня смущает только один момент - не могу придумать, как реализовать подсказку "больше-меньше" и соответствующие шаги. буду благодарен за совет.
P.s. если все же сам смогу решить, напишу код сюда.
Еще раз спасибо!
смотри компьютер всегда будет делить доступный range на 2 и говорить пользователю середину. а пользователь говорит больше или меньше. У нас в коде это были if() в которых мы сравнивали с target. тут тебе надо давать пользователю выбрать и его ответ подставить в if
@@frontendscience да, это понятно, что if решает. Но, я когда пытался сделать это, он получался многоэтажный, что не есть хорошо.
В итоге я сделал чуть иначе, подсмотрев идею в другом проекте. Там на кнопки ставили обработчик события, и в зависимости от нажатой кнопки сдвигали верхний и нижний пределы.
Отличная идея
@@frontendscience спасибо. Но, увы, в целом она не моя.
Я только применил ее в своей ситуации
@@stastikhomirov8075 ну не всегда надо велосипед изобретать! Успехов
Благодарю
Добрый день, подскажите пожалуйста в какой программе работали в этом видео?
В смысле, в какой программе создавал видео?
@@frontendscience Извиняюсь за неточный вопрос, в чём написать такой алгоритм, чтобы его можно было запустить?
Я часто использую сайт codepen для этого
@@frontendscience Спасибо!
Спасибо за видео!
только не совсем понимаю зачем усложнять когда можно просто воспользоваться методом arr.indexOf(serchElem) ?
но при нестандартных ситуациях наверное необходимо знать такие алгоритмы - существенно сократят время и ресурсы машины.
кстати, возник логичный вопрос - какой метод поиска использует метод arr.indexOf(serchElem) , линейный или бинарный?
Проверил, алгоритм array.indexOf(searchElem) проигрывает 15 секунд бинарному алгоритму поиска при 10млн. элементах в массиве для поиска.
Сергей, а можно этот алгоритм использовать для строчных типов данных?
У строк есть свой метод indexOf.
IndexOf у массивов линейный, так как для бинарного поиска нужна сортировка а indexOf работает для любого порядка элементов
Не понял зачем ((right - left)/ 2) + left. Мы же ниже всё равно меняем позицию left, нет?
Нормальные люди махом вычисляют средний индекс: (right+left)/2. Автор почему-то решил отдельно вычислять полудлину диапазона поиска, а потом отдельно добавлять смещение левого края, чтобы найти в итоге тот же средний индекс. По математике выражения эквивалентны, так что всё нормально. Только компьютеру лишние действия, но когда фронтендщики переживали на этот счет :-)
@@alexuspro26 В решение ((right - left)/ 2) + left используется более маленькие числа, и из этого следует, что нужно меньше памяти.
@@surensamarchyan7230 JS любое число хранит в 64 битах. Числа 34 и 7346752 занимают одинаковое количество памяти. Если же Вы собираетесь хранить и обсчитывать строки, но думаете о битах, то подумайте о тактах. В общем, не убедили.
Все по очереди
Простите за глупый вопрос. Я не понимаю, зачем в мид надо приплюсовывать лефт?
У випадку, якщо шуканий елемент буде правіше середини, після переприсвоювання лефт в наступному циклі середину буде знайдено неправильно, тобто вона буде менша за лефт.
@@_vasyl_5039 дякую))
В случае, если искомый элемент будет правее середины, после переприсваивания лет в следующем цикле середина будет найдена неправильно, то есть она будет меньше лефт.
1:54
а почему если определить значение mid сразу при объявлении переменной - код не работает?
Потому что при следующем цикле mid должен обновиться исходя их новых значений right и left.
@@nicealx спасибо
Хммм, я бы заменил 9 строку на mid = Math.round((left + right)/2); Тут будет меньше текста, а работает аналогично.
Разрешаю )
а как насчет того случая, когда у нас искомый элемент в массиве не один? можно усугубить - ненужные тоже, по крайней мере, несколько. в телефонной книге, с которой Вы начали, будет, именно, так. или интервьюеры этого, почти наверняка, не понимают. кстати, это еще и по поводу популярной сентенции, что математика и образование для программиста не обязательны. и еще. бинарный поиск - это лучше чем перебор, но это не оптимальный алгоритм.
Кейс когда есть повторы - тоже не проблема. Сортируем. С помощью бинарного поиска ищем любой из дубликатов. потом двумя указателями расходимся влево и вправо - находим границы всех повторов.
А какой по вашему мнению будет самы оптимальный вариант поиска в таком случае?
Интересует, как объяснять алгоритм индекса на основе бинарных деревьев.?
Когда-нибудь мы до них дойдем)
из какого мультика улитка на 1 30?
«Университет монстров».
Нужно собрать мегаминкс)
А можно еще попросить о python рассказать?
Извините, я по Js.
@@frontendscience хорошо. Спасибо, js мне тоже нужен. У вас самое понятное объяснение.
Js и python похожи. Ты просто можешь адаптировать этот код под синтаксис python. Насколько знаю нужно просто по-другому массив назначить и убрать фигурные скобки
Тут косяк, при 1 млн, нужно не млн итераций, если делать обычным перебором O(n) и если искомая фамилия последняя, достаточно 1млн-1, следовательно с 2млн соответственно
Красно черные деревья))
Не уверен, что такое спросят на фронтенд разработчика - скорее это фулстэк или бэкенд. Но я подумаю. Благодарю)
А если массив не отсортированный?
Тогда бинарным поиском не получится решить.
@@frontendscience Если выпадет на mid или искомый элемент справа отсортирован, то получится : )
бинарный поиск это поиск строго по очереди от 0 до 100 допистим или может быть 25,14,15,3...????
Сказали же, строго отсортированный массив.
Дякую
не проще L + R / 2 ?
Число может оказаться не целым
@@kalts_daniil Math.floor((l + r)/2)
че за имена? Шелдон Пени? это на сорта яблок больше похоже
в моём счастливом советском детстве этот метод назывался просто: "метод деления пополам"... 😝
pied piper ☺
Да но массив данных должен быть отсортированным.
Да должен быть!
@@frontendscience сортируем пущырьком и получаем O(n2) :D
Алгоритм перестановки без повторений. Пример число 5 = 0000012345
Ахах, как видите все очень просто. 😀
((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
Но в программировании есть свои ньюансы, поэтому лучше употреблять первое выражение. можно конечно употребить второе, но только если Вы точно уверены, что оно сработает правильно. А оно не всегда может сработать правильно, ибо есть такая штука как переполнение.