⚛⚛⚛ Пройди практический курс "Javascript Fullstack разработчик" от MakeWeb.me. Детали тут: makeweb.me/course-js-fullstack-developer Телеграм для связи по курсу: @makewebchatme
То шо надо! Давно пора бы появиться на русском ютубе подобным видео. Немного больше разжевывания не помешало бы, но в целом подача материала хороша и голос приятный. Спасибо, лайк!
Уважаемый, ты хорош. Благодаря тебе я только что понял бинарный поиск, за два года карьеры.) Если непонятно кому, советовал бы выполнять код в голове - просчитывать значения переменных на каждом шаге, хотя бы условно. А если непонятны логарифмы, то просто запомнить принцип - некоторые стандартные алгоритмы хороши для огромных отсортированных массивов.
Только как неделю начал изучать JS, посмотрев видео сначала ничего не понял, посмотрел второй раз мало что понял, посмотрел видео на след. день и меня просветило, наконец-то понял! Вот только с определением сложности задачи пока туго, пересмотрю видео через время, может тоже просветит)
Всем привет! Автор видоса здесь 👋 Если есть желание подробнее разобраться в бинарном поиске на практических примерах, я сделал плейлист с решениями задачек с LeetCode на эту тему - ruclips.net/p/PLtRFPaw3fD5647YtyPCXcuVlGOUrMBgks PS. У меня на канале каждый вторник, в 20 по Мск, проходят стримы с решениями алгоритмических задач. Welcome!
Здравствуйте, а я не очень понимаю какая в итоге получится сложность последней функции? Я так понимаю О(N*logN) - это сложность встроенного метода sort и О(logN) это сложность бинарного поиска, опустив ее получается можем сказать, что общая сложность - О(N*logN) ?
) чего только разработчики высокоуровневых языков не сделают лишь бы не работать на работе. Для поиска есть .find Для фильтров есть .filter Также есть .some .indexOf и прочее. В браузерах обычно мы не пишем ракеты летящие на Марс.
Только начинаю знакомство с алгоритмами. Вопрос относительно бинарного поиска. Понятно, что он эффективнее линейного, но сама сортировка та еще задача. Почему опускается алгоритм сортировки при сравнении? Это как сравнивать соленое с квадратным.
Хороший вопрос, спасибо. В видео говорится, что прежде чем запускать бинарный поиск требуется выполнить сортировку, соответсвенно всё зависит от того сколько этих самых поисков предполагается выполнить. Если нужно найти элемент всего один раз - нет смысла сортировать, проще линейный поиск запустить, но если поиск нужно выполнить миллион раз, имеет смысл сперва потратить время на сортировку. Где этот самый порог - зависит от конкретного случая, поэтому в реальном проекте имеет смысл профилировать.
Добрый день, подскажите, как переписать данный поиск чтобы он искал не только точный элемент но и больше\равно. Например: Есть массив [5,10,15,38,49,104]. И если попытаться найти элемент, скажем 18 чтобы возвращало индекс числа 49, если 14 то индекс 15. То есть не только элемент но и >= элемент. Спасибо
Круууууть! Прекрасная тема. Я этим в свое время занимался, только на 1С и я реализовывал разные сортировки. Единственное я не понял: почему второй вариант называется бинарным?
Какой именно вариант? Второй была задача подсчёта частоты вхождений, есть вариант её решения с помощью бинарного поиска - как демонстрация где может использоваться бинарный поиск.
Else избыточен. Если условие выполнится, то функция вернет результат и строки дальше выполняться не будут. Зачем писать больше? Например, такие записи идентичны: 1). if (condition) { return true; } else { return false; } 2). Скобочки для однострочного условия можно тоже опустить. if (condition) return true; return false; В коде из видео я не увидел return -1 после условия, только после цикла. Но, надеюсь, я правильно понял ваш вопрос. Успехов!
Почитай как нибудь на досуге книжку "Грокаем алгоритмы" там про все популярные алгоритмы (вкл. бинарный поиск) рассказывается максимально простым языком
@@ПавелРузанкин-м1ж Спасибо. На днях купил эту книгу. Читаю на стр.20 Что необходимо знать Чтобы читать эту книгу, необходимо знать базовую алгебру. Например, возьмем следующую функцию: f(x) = x * 2. Чему равен результат f(5)? Если вы ответили "10" - читайте спокойно. Если бы эта простая задачка была задана на JavaScript, я бы ее решил быстро. Но с алгеброй все очень плохо (школа давно в прошлом, уже 43 :) ). Чтобы построить алгоритмы, нужно на отлично алгебру знать? Или алгоритмы это must have только если продукт надо кодить?
@@MishaWS Чтобы строить алгоритмы, достаточно обладать логическим мышлением, не более того. А все классические алгоритмы, которые приводятся в книги, нужны по сути для работы с большими данными (не big data science) для быстрой сортировки и нахождения правильного результата
зачем давать уроки с неправильными решениями ? ваши уроки только вредят тогда а не помагают), в примере все будет работать только если нет повторяющигся елементов, например найти в масиве [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; }
Спасибо за комментарий, выходит вы пытались проверить этот код и разобраться - а говорите видео бесполезные :-) Не очень понимаю пока что не работает, давайте на конкретном работающем коде проверим - codepen.io/vitkarpov/pen/XWmjzMp , вот код из видео на вашем примере, показывает мне что 56 находится под индексом 10. Что именно не работает?
Viktor Karpov Да но находит ближащий елемент, а так вобще не находит, тогда нужно в видно уточнить что пример работает только с таким типом списка, где только уникальние числа.
@@samogray86 так стоп, а почему вы пытаетесь применить бинарный поиск на несортированном списке? это так не работает :-) и мой пример выше невалидный, про неопределенное поведение, так просто нельзя алгоритм использовать.
⚛⚛⚛
Пройди практический курс "Javascript Fullstack разработчик" от MakeWeb.me.
Детали тут: makeweb.me/course-js-fullstack-developer
Телеграм для связи по курсу: @makewebchatme
Спасибо за качественный и полезный контент!
То шо надо! Давно пора бы появиться на русском ютубе подобным видео. Немного больше разжевывания не помешало бы, но в целом подача материала хороша и голос приятный. Спасибо, лайк!
Уважаемый, ты хорош. Благодаря тебе я только что понял бинарный поиск, за два года карьеры.)
Если непонятно кому, советовал бы выполнять код в голове - просчитывать значения переменных на каждом шаге, хотя бы условно. А если непонятны логарифмы, то просто запомнить принцип - некоторые стандартные алгоритмы хороши для огромных отсортированных массивов.
Спасибо за фидбек. Запилил специальный тредик про логарифм в твитере - twitter.com/vitkarpov/status/1342828952113577984
Спасибо! Чётко, ясно и понятно!
Это лучшее, что я встречал про алгоритмы. огромное спасибо
ты очень крутой!!!!! Спасибо за видео(начала разработку на js, с этого урока понятно, как структурировать и изучать информацию)
Только как неделю начал изучать JS, посмотрев видео сначала ничего не понял, посмотрел второй раз мало что понял, посмотрел видео на след. день и меня просветило, наконец-то понял! Вот только с определением сложности задачи пока туго, пересмотрю видео через время, может тоже просветит)
Долго искала нечто такое! Спасибо вам! Это действительно качественный контент :3
Всем привет! Автор видоса здесь 👋 Если есть желание подробнее разобраться в бинарном поиске на практических примерах, я сделал плейлист с решениями задачек с LeetCode на эту тему - ruclips.net/p/PLtRFPaw3fD5647YtyPCXcuVlGOUrMBgks
PS. У меня на канале каждый вторник, в 20 по Мск, проходят стримы с решениями алгоритмических задач. Welcome!
Я так понимаю, подобные примеры и объяснения взяты из книги "Грокаем алгоритмы".
Подача хорошая и интересная)) спасибо)
Ты крут!) Спасибо за тему алгоритмов с использованием JS! Можно еще продолжения этих уроков?
Спасибо, надеюсь полезно! Будем продолжать.
Спасибо за работу, очень полезные уроки!
почему left = -1? равзе он не начнет с конца массива?? так же как и arr.length
тоже не понял почему -1, а не 0
потому что -1 = граница, за которой точно нет элемента, тк поиск начнется с 0
Здравствуйте, а я не очень понимаю какая в итоге получится сложность последней функции? Я так понимаю О(N*logN) - это сложность встроенного метода sort и О(logN) это сложность бинарного поиска, опустив ее получается можем сказать, что общая сложность - О(N*logN) ?
Супер. Жду не дождусь видео по другим алгоритмам
спасибо добавил в спонсорблок рекламу . просьба проголосовать
Непонятно, почему за начальный элемент массива мы берем -1 а не 0, ведь элемента с индексом -1 в массива не существует
) чего только разработчики высокоуровневых языков не сделают лишь бы не работать на работе.
Для поиска есть .find
Для фильтров есть .filter
Также есть .some .indexOf и прочее.
В браузерах обычно мы не пишем ракеты летящие на Марс.
Всё верно. Противоречий нет.
ну ведь нужно понимать, как это работает под капотом.
Супер круто, спасибо.
четко все объяснили :)
Только начинаю знакомство с алгоритмами. Вопрос относительно бинарного поиска. Понятно, что он эффективнее линейного, но сама сортировка та еще задача. Почему опускается алгоритм сортировки при сравнении? Это как сравнивать соленое с квадратным.
Хороший вопрос, спасибо. В видео говорится, что прежде чем запускать бинарный поиск требуется выполнить сортировку, соответсвенно всё зависит от того сколько этих самых поисков предполагается выполнить. Если нужно найти элемент всего один раз - нет смысла сортировать, проще линейный поиск запустить, но если поиск нужно выполнить миллион раз, имеет смысл сперва потратить время на сортировку. Где этот самый порог - зависит от конкретного случая, поэтому в реальном проекте имеет смысл профилировать.
Очень интересно
Добрый день, подскажите, как переписать данный поиск чтобы он искал не только точный элемент но и больше\равно. Например:
Есть массив [5,10,15,38,49,104]. И если попытаться найти элемент, скажем 18 чтобы возвращало индекс числа 49, если 14 то индекс 15. То есть не только элемент но и >= элемент. Спасибо
То, о чем вы говорите похоже на upper_bound. Можно, например, вот так: codepen.io/vitkarpov/pen/ZEpVKPx?editors=0010
Вот тут я показывал живой пример реализации двоичного поиска на микроконтроллере:
ruclips.net/channel/UCETNBYBk4IA0rSHCnp2jnhQ
Круууууть! Прекрасная тема. Я этим в свое время занимался, только на 1С и я реализовывал разные сортировки. Единственное я не понял: почему второй вариант называется бинарным?
Какой именно вариант? Второй была задача подсчёта частоты вхождений, есть вариант её решения с помощью бинарного поиска - как демонстрация где может использоваться бинарный поиск.
странно бинарный поиск работает только с сортировкой num.sort((a, b) => a - b);
В этом вся суть алгоритма. Если массив не отсортирован, то нет никакой возможности понять при делении пополам искомое значение слева или справа.
А почему return -1 пишется не в else, например?
Else избыточен. Если условие выполнится, то функция вернет результат и строки дальше выполняться не будут. Зачем писать больше?
Например, такие записи идентичны:
1).
if (condition) {
return true;
} else {
return false;
}
2). Скобочки для однострочного условия можно тоже опустить.
if (condition) return true;
return false;
В коде из видео я не увидел return -1 после условия, только после цикла. Но, надеюсь, я правильно понял ваш вопрос. Успехов!
@@cherniaev спасибо
У сортировки сложность больше чем O(n).
Я бы теорию добавил, практика для начинающих быстровата.
Спасибо. Если 95% не понял, что посоветуете? Хотя JavaScript очень нравится и хочу на нем код профессионально писать.
Почитай как нибудь на досуге книжку "Грокаем алгоритмы" там про все популярные алгоритмы (вкл. бинарный поиск) рассказывается максимально простым языком
@@ПавелРузанкин-м1ж Спасибо. На днях купил эту книгу. Читаю на стр.20
Что необходимо знать
Чтобы читать эту книгу, необходимо знать базовую алгебру.
Например, возьмем следующую функцию: f(x) = x * 2.
Чему равен результат f(5)? Если вы ответили "10" - читайте спокойно.
Если бы эта простая задачка была задана на JavaScript, я бы ее решил быстро.
Но с алгеброй все очень плохо (школа давно в прошлом, уже 43 :) ).
Чтобы построить алгоритмы, нужно на отлично алгебру знать?
Или алгоритмы это must have только если продукт надо кодить?
@@MishaWS Чтобы строить алгоритмы, достаточно обладать логическим мышлением, не более того. А все классические алгоритмы, которые приводятся в книги, нужны по сути для работы с большими данными (не big data science) для быстрой сортировки и нахождения правильного результата
Привет. Можно начать с ruclips.net/p/PLtRFPaw3fD55QtDdLVruhKa0M9Wv1l3SR где я разбираю всё с нуля и очень-очень подробно.
Я так понял это не для новичков, а кто давно в теме?!))
Потому что все пишут: «хорош объяснил! Все понятно», только я нечего не понял))))
Если вы сформулируете вопрос, мы попробуем на него ответить :-)
Мозг.
зачем давать уроки с неправильными решениями ? ваши уроки только вредят тогда а не помагают), в примере все будет работать только если нет повторяющигся елементов, например найти в масиве [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;
}
Спасибо за комментарий, выходит вы пытались проверить этот код и разобраться - а говорите видео бесполезные :-) Не очень понимаю пока что не работает, давайте на конкретном работающем коде проверим - codepen.io/vitkarpov/pen/XWmjzMp , вот код из видео на вашем примере, показывает мне что 56 находится под индексом 10. Что именно не работает?
Более полный набор тестов можно найти здесь - leetcode.com/problems/binary-search/ . Давайте проверим там.
Другой вопрос, что если элементы повторяются, то вообще говоря получаем неопределённое поведение - то ли один найдётся, то ли другой.
Viktor Karpov Да но находит ближащий елемент, а так вобще не находит, тогда нужно в видно уточнить что пример работает только с таким типом списка, где только уникальние числа.
@@samogray86 так стоп, а почему вы пытаетесь применить бинарный поиск на несортированном списке? это так не работает :-) и мой пример выше невалидный, про неопределенное поведение, так просто нельзя алгоритм использовать.