@@F1x_SerGo я не ждал, я просто у его спрашивал, я и так свои структуры писал на с++ да и не мало, и туда семафоры, мьютексы, дедлоки, конкурентные очереди, атомиксы, ф'ючеры... оно мне не нужно
Спасибо большое)) Марафон от Наиля прошел, продвинутую Java прошел, Spring прошел, теперь очередь алгоритмов)) Люди пишут в комментариях можно ли упростить запись до (high + low) / 2; Я всегда люблю разбираться в коде, пока мне не станет понятно, почему так должно быть. Если мы возьмем ручку и бумагу, и сделаем все вычисления например число 20, как в примере Наиля при формуле (high + low) / 2; - будет 4 итерации, а если мы берем формулу low + (high - low) / 2; то будет 3 итерации, как и сказано при расчете логарифма. Я читаю книжку и смотрю дополнительно видео Наиля совмещаю два в одном, всем тоже рекомендую, лучше несколько источников открыть информации, сравнить и понять еще будет легче, но Наиль всегда объясняет на высоте))
"Грокаем" -- в книге "Алгоритмы" хорошо объяснил как работает бинарный поиск, здесь увидел грамотно разложенную реализацию. Так что несколько источников это большой +. Согласен.
Дело не в количестве итераций, а в том, что, если мы применим формулу (high + low) / 2, то мы можем выйти за границы int'a в случае, если оба слагаемых больше 10^30.
Можно улучшить алгоритм двоичного поиска на 10-й минуте. В первой итерации мы сравниваем число в массиве(16), а затем если оно не равно - оставляем почему то его в следущем массиве. Из-за этого итераций больше.
Наиль, здравствуйте! Большое спасибо за все Ваши курсы, все очень понятно и интересно. Скажите, пожалуйста, будет ли продолжение данного курса "Алгоритмы и Структуры данных"?
Здравствуйте, очень хотелось бы увидеть Spring, а вообще, большое спасибо за уроки и объяснения, хотелось бы по возможности больше роликов, уверен это будет круто и полезно что зрителям, что вам, сабскрайберов добавится однозначно... Спасибо еще раз!
Спасибо за курс! Всё доходчиво и ясно. Будет ли продолжение? Пока что по большому счёту затронуты только два алгоритма - жадный алгоритм и бинарный поиск + вообще не затронули структуры данных (работали только с массивом в рамках данного курса)
а как же сложность сортировки? т.е. если мы имеем дело с неотсортированным массивом, то нам сначала нужно его отсортировать, а уж потом искать в нем бинарным поиском. А это уже сложность (применяя алгоритм быстрой сортировки или сортировки слияния) O(n*log(n)) ... а это уже больше чем O(n). Получается, что если нам дан не отсортированный массив, то для поиска нужно применять линейный поиск?
Ты абсолютно прав. Методом простого перебора я среди миллиарда чисел нужно нашёл почти в 5 раз быстрее. Но помни, что тебе в любой другой момент написания программы может понадобится, например 1827412 элемент упорядоченного массива, и чтобы заново его не искать, можно сразу упорядочить элементы
только проблема в том, что сам массив обычно приходит неотсортированным. А сложность его сортировки N * log(N). Соответственно, суммарная сложность будет N * log(N) + log(N) ~ N * log(N)
Здравствуйте. Очень приятно смотреть ваши уроки. Но что то мне немного не понятно. В начале видео стояла задача определить индекс заданного элемента в неотсортированной последовательности, а бинарный поиск находит определенный элемент в отсортированной последовательности, это немного разные задачи. Если мы хотим применить бинарный поиск применить к первой задаче, необходимо вводить второй массив для индексов и сортировать первый, а это уже другая сложность алгоритма, большая О(n). Или я ошибаюсь??? Заранее спасибо за ответ .
Здравствуйте! Видимо я недостаточно понятно этот момент объяснил. Задача стоит найти элемент в массиве. Неважно, отсортированный он или нет. Конечно чаще всего, в реальной жизни, массив бывает не отсортированным. Для того, чтобы ускорить поиск, мы этот массив сортируем. И конечно на сортировку мы должны задействовать вычислительные ресурсы (сложность сортировки O(N*log(N)). Но зато, благодаря сортировке (которая происходит один раз), мы теперь можем каждый раз находить элемент в массиве не за O(N), а за O(log(N)). Еще раз замечу: алгоритм двоичного поиска выгодно использовать только в том случае, если мы собираемся часто искать индекс элемента в этом массиве. Тогда начальная плата за сортировку O(N*log(N)) будет стоить того, чтобы потом очень быстро находить индекс элемента в отсортированном массиве. Если же нам надо только один раз найти индекс элемента в массиве, то выгодней просто пройтись по нему за O(N).
В целом хорошо. Но после того как написали код, то его нужно было запускать в режиме пошагового выполнения хотя бы первые две итерации, с тем чтоб проиллюстрировать значения переменных, т.е. то, что вычисления производятся верно.
@@alishevN Спасибо за объяснения алгоритма все доходчиво, кроме формулы. Просто чуть время на ней потерял)Но, ваш способ подходит лучше для операций с указателями, т.к. складывать указатели нельзя, а вот отнимать можно)
Отличный материал для чайников, то что мне нужно. Не понял одного про бинарный поиск: если у нас к-во элементов в массиве нечетное, то формула нахождения середины (high + low) / 2 не будет работать, т.к. не даст целого числа для определения индекса середины массива. Странно, что автор не упомянул про это.
@@АлишерТоктомушев-щ7л Купи книжку "Грокаем Алгоритмы" Или еще лучше, я ее на днях перепроходить буду можешь добавиться в дискорде - МОЖЕМ ПАВТАРИТЬ!111!!#2257 Обычно я переписываю в цеттеле все конспекты, и буду переписывать темы из книги, сможем обсудить и порешать представленные там задачки.
@@АлишерТоктомушев-щ7л Я не знаю как это замерить) Вообще прошел курс наиля на юдеми, сейчас вот перепройду книжку, затем java ee и за андроид разработку возьмусь, еще котлин нужен будет.
Очень жаль, что нет продолжения курса, но та часть, что есть уже очень хороша, спасибо! Единственный вопрос со сложностью, согласен что осуществлять бинарный поиск гораздо быстрее, но он ведь работает только в отсортированном массиве. Получается что если у нас есть не отсортированный массив в котором нужно найти значение, нужно его сначала отсортировать. В итоге получаем сложность сортировки массива n*log(n) и после сортировки бинарный поиск у которого сложность log(n), так как n*log(n) хуже чем log(n) получаем конечную сложность этого алгоритма n*log(n), что ощутимо дольше при больших объемах данных чем поиск значения в не отсортированном массиве сложность которого равна О(n) и лучше в таких случаях использовать классический линейный поиск в не отсортированном массиве. Но конечно все еще зависит от того как дальше будут использоваться эти данные
Здравствуйте. Видео хорошее, вполне всё понятно, плюс книжка "Грокаем алгоритмы" под боком, но возник вопрос, а каким образом бинарным поиском находят слово в словаре? Потому что судя по той же книге и вашему видео я понял, что алгоритм перебирает только цифры... тем более логарифмическая функция
Скорее всего вы ответ уже знаете)) Но для тех, кто также задастся этим вопросом, то класс String имплементирует интерфейс Comparable, соответственно для сравниния нужно вызывать метод compareTo
Рекурсивное решение от новичка: public static int binarySearch (int[] arr, int number, int low, int high){ int middle=0; middle=low+(high-low)/2; if (number==arr[middle]){ return middle; } else if (low==high){ return -1; }else if (numberarr[middle]){ return binarySearch(arr,number,middle+1,high); } else return middle; }
хорошее видео, я бы порекомендовал еще книжку "Грокаем алгоритмы" я ее проглатил за обе щеки за 3 вечера и самое главное, в моей тупой голове даже что-то отложилось
я конечно все понимаю, но не один человек на ютубе не обьясни, что делать если ключей в массиве несколько и надо подсчитать их колличество и вывести индексы
Создай массив для этих клучов и с помощью цикла поставь эти ключи. Вот так 👇 int[] keys = {3, 5, 7, 9}; for (int i = 0; i < keys.length; i++) birnarySearch(здес массив, keys[i] ); Примерно так. Дальше сам делай
КУРС ПО GIT: www.udemy.com/course/git-alishev/?referralCode=71994763964B8E2E6A4E
Отличные видео по алгоритмам, хотелось бы продолжение!
СПАСИБО БОЛЬШОЕ!!! САМОЕ ГОДНОЕ ЧТО ЕСТЬ В ИНТЕРНЕТЕ! САМЫЙ КРУТОЙ КУРС ПО АЛГОРИТМАМ! ПОЖАЛУЙСТА ПРОДОЛЖИТЕ КУРС!!!!
оу оу оу)
Лучшее видео по бинарному поиску! Наконец поняла сложность! Спасибо!
Самое лучшее объяснение бинарного поиска которое я когда-либо слышал!
видео отличное. от себя хочу сказать, что советую книгу гракаем алгоритмы
Наиль, спасибо вам огромное за ваши уроки! Очень интересные и полезные! Теперь буду изучать ваш курс по языку Python.
Смотрю этот курс и параллельно занимаюсь в N - Вы объясняете гораздо понятнее преподавателя из N. Спасибо за все Ваши курсы, смотрю с интересом.
Спасибо большое! С нетерпением жду следующие видео по алгоритмам и структурам данных
Максим Андреевич ну как ждёшь ещё?
Еще ждешь?
@@ruslanvolovik2745 дождался?)
@@F1x_SerGo я не ждал, я просто у его спрашивал, я и так свои структуры писал на с++ да и не мало, и туда семафоры, мьютексы, дедлоки, конкурентные очереди, атомиксы, ф'ючеры... оно мне не нужно
@@F1x_SerGo а ты дождался?)
Спасибо за уроки. Просто, понятно и интересно
компьютерные боги услышали меня, спасибо Наиль
Спасибо большое)) Марафон от Наиля прошел, продвинутую Java прошел, Spring прошел, теперь очередь алгоритмов))
Люди пишут в комментариях можно ли упростить запись до (high + low) / 2;
Я всегда люблю разбираться в коде, пока мне не станет понятно, почему так должно быть.
Если мы возьмем ручку и бумагу, и сделаем все вычисления например число 20, как в примере Наиля при формуле (high + low) / 2; - будет 4 итерации, а если мы берем формулу low + (high - low) / 2; то будет 3 итерации, как и сказано при расчете логарифма.
Я читаю книжку и смотрю дополнительно видео Наиля совмещаю два в одном, всем тоже рекомендую, лучше несколько источников открыть информации, сравнить и понять еще будет легче, но Наиль всегда объясняет на высоте))
"Грокаем" -- в книге "Алгоритмы" хорошо объяснил как работает бинарный поиск, здесь увидел грамотно разложенную реализацию. Так что несколько источников это большой +. Согласен.
Дело не в количестве итераций, а в том, что, если мы применим формулу (high + low) / 2, то мы можем выйти за границы int'a в случае, если оба слагаемых больше 10^30.
если применить математику и раскрыть скобки, то вы увидите, что
low + (high - low) / 2 = (high + low) / 2
Ждем продолжения)
Ждем-с продолжения, отлично объясняешь.
Очень доходчиво, спасибо!
Боже, Алишев, ты просто топ
Спасибо большое за подробные и качественные объяснения
отличный курс, хотелось бы продолжение!
СПАСИБО!!! ОСОБЕННО ЗА САМОСТОЯТЕЛЬНЫЕ ЗАДАЧИ!
Блин, всегда с удовольствием смотрю, все подробно рассказано.Спасибо.
офигенски объясняете , спасибо за видео !
Можно улучшить алгоритм двоичного поиска на 10-й минуте. В первой итерации мы сравниваем число в массиве(16), а затем если оно не равно - оставляем почему то его в следущем массиве. Из-за этого итераций больше.
не можно, а нужно. Поскольку индекс мида больше индекса 13-ти, то мид отбрасывается тоже. Автор ошибся
Спасибо большое! Ждём продолжения в 2022 году!
А будет ли продолжение? Очень уж курс хороший, жалко, если забросите))
Большое спасибо за урок!
Отличное объяснение!!!
все очень понятно спсибо болльшое за уроки !!
Наиль, здравствуйте! Большое спасибо за все Ваши курсы, все очень понятно и интересно. Скажите, пожалуйста, будет ли продолжение данного курса "Алгоритмы и Структуры данных"?
Здравствуйте, Рушанна!
Да, будет.
Здравствуйте, Рушанна!
Конечно же нет
@@ministryNoiz еще ждешь?
@@ministryNoiz я в шоке 😱
Надеюсь обьяснять не придется
Прошел еще один год
public static int binarySearch(int[] sortedArray, int key, int low, int high){
int mid = low + (high - low) / 2;
if (low > high ) return -1;
if (key < sortedArray[mid]) return binarySearch(sortedArray, key, low, mid -1);
else if (key > sortedArray[mid]) return binarySearch(sortedArray, key, mid + 1, high);
else return mid;
}
ChatGPT подсказал, что лучше base case поставить перед вычислением mid, чтобы не выполнять лишнее вычисление (видимо)
спасибо за видео, очень доступно
привет из 2022 твои видео до сих пор учат людей можешь продолжать свою рубрику или делать новые уроки очень интересно учишь
Наиль здравствуйте, а будет продолжение? И спасибо за урок)
Здравствуйте, очень хотелось бы увидеть Spring, а вообще, большое спасибо за уроки и объяснения, хотелось бы по возможности больше роликов, уверен это будет круто и полезно что зрителям, что вам, сабскрайберов добавится однозначно... Спасибо еще раз!
Спасибо!
Spring хочу начать записывать скоро.
будет продолжение? как было сказано "изучим в этом курче"?
наверное нет
Отличное видео
Добрый день! Замечательное видео, стало все понятно после просмотра. Прошу подсказать разницу в написание следующей строки. В чем разница ""int middle = (left + right) / 2"" и ""int middle = low + (high - low) / 2""
Спасибо огромное!
Спасибо за курс! Всё доходчиво и ясно. Будет ли продолжение?
Пока что по большому счёту затронуты только два алгоритма - жадный алгоритм и бинарный поиск + вообще не затронули структуры данных (работали только с массивом в рамках данного курса)
а как же сложность сортировки? т.е. если мы имеем дело с неотсортированным массивом, то нам сначала нужно его отсортировать, а уж потом искать в нем бинарным поиском. А это уже сложность (применяя алгоритм быстрой сортировки или сортировки слияния) O(n*log(n)) ... а это уже больше чем O(n).
Получается, что если нам дан не отсортированный массив, то для поиска нужно применять линейный поиск?
Ты абсолютно прав.
Методом простого перебора я среди миллиарда чисел нужно нашёл почти в 5 раз быстрее.
Но помни, что тебе в любой другой момент написания программы может понадобится, например 1827412 элемент упорядоченного массива, и чтобы заново его не искать, можно сразу упорядочить элементы
Ну а время на сортировку массива?
только проблема в том, что сам массив обычно приходит неотсортированным. А сложность его сортировки N * log(N). Соответственно, суммарная сложность будет N * log(N) + log(N) ~ N * log(N)
И это все еще лучше, чем O(n)
@@АнатолийГлушков-у4м чем O(n * log(n)) лучше, чем O(n) ?
Здравствуйте. Очень приятно смотреть ваши уроки. Но что то мне немного не понятно. В начале видео стояла задача определить индекс заданного элемента в неотсортированной последовательности, а бинарный поиск находит определенный элемент в отсортированной последовательности, это немного разные задачи. Если мы хотим применить бинарный поиск применить к первой задаче, необходимо вводить второй массив для индексов и сортировать первый, а это уже другая сложность алгоритма, большая О(n). Или я ошибаюсь??? Заранее спасибо за ответ .
Здравствуйте!
Видимо я недостаточно понятно этот момент объяснил.
Задача стоит найти элемент в массиве. Неважно, отсортированный он или нет. Конечно чаще всего, в реальной жизни, массив бывает не отсортированным. Для того, чтобы ускорить поиск, мы этот массив сортируем. И конечно на сортировку мы должны задействовать вычислительные ресурсы (сложность сортировки O(N*log(N)).
Но зато, благодаря сортировке (которая происходит один раз), мы теперь можем каждый раз находить элемент в массиве не за O(N), а за O(log(N)).
Еще раз замечу: алгоритм двоичного поиска выгодно использовать только в том случае, если мы собираемся часто искать индекс элемента в этом массиве. Тогда начальная плата за сортировку O(N*log(N)) будет стоить того, чтобы потом очень быстро находить индекс элемента в отсортированном массиве. Если же нам надо только один раз найти индекс элемента в массиве, то выгодней просто пройтись по нему за O(N).
@@alishevN Spasibo, vot etot moment ocen vazen, kak ras tokoj vapros u menia byl.
Простое как 2 бита
В целом хорошо. Но после того как написали код, то его нужно было запускать в режиме пошагового выполнения хотя бы первые две итерации, с тем чтоб проиллюстрировать значения переменных, т.е. то, что вычисления производятся верно.
10:24 зачем число 16 в новый подмассив включать, если точно знаем, что это не 13?
не нужно и в реализации, которая приводится далее 16 не будет включено.
В формуле, если упростить выражение получится (2Low +High - Low)/2 =>
( Low + High)/2 . Так и не понял зачем такую формулу писать .
Можно сделать так, как вы предлагаете. Я использовал более интуитивно понятную формулу.
@@alishevN Спасибо за объяснения алгоритма все доходчиво, кроме формулы. Просто чуть время на ней потерял)Но, ваш способ подходит лучше для операций с указателями, т.к. складывать указатели нельзя, а вот отнимать можно)
Здравствуйте, Наиль.
Всё хочу узнать, как там дела с курсом по Spring-у ?
Присоединяюсь к данному оратору
Я кстати только-что купил курс "продвинутая java" от Наиля на udemy, думаю, оно того стоит. Но опять же очень жду Spring :)
Ждёте?
@@curtisaxel4291 еще ждешь?
на минуте 5:19 ошибка на слайде. Там должно быть наоборот если к больше то смотрим правый подмассив, если к меньше то смотрим левый.
"смотрим число в центре" Оно больше k ?
А где продолжение курса? Хотя бы платный
А будет продолжение?
Вообще планирую, но не в ближайшем будущем.
@@alishevN жаль (
Отличный материал для чайников, то что мне нужно. Не понял одного про бинарный поиск:
если у нас к-во элементов в массиве нечетное, то формула нахождения середины (high + low) / 2 не будет работать, т.к. не даст целого числа для определения индекса середины массива.
Странно, что автор не упомянул про это.
А можно преобразовать формулу нахождения среднего в такую: (low+high)/2 ? Её никогда не приводят в уроках, может есть подвох в целочисленном делении?
вроде как в грохаем алгортмы такая)
@@ViktorAr2023 В общем, если использовать эту формулу то может случится переполнение при сложении. Поэтому используют low+(high-low)/2.
@@Игорь-з7о1м Arrays.binarySearch() )) в языке уже написано все, принципе и норм
благодарю
Жаль что автор забросил данную ветку очень хорошее начало ... я бы даже на юдеме купил бы )
Да а что делать я начал изучать по этому каналу дальше продолжении нет я в тупике
@@АлишерТоктомушев-щ7л Купи книжку "Грокаем Алгоритмы" Или еще лучше, я ее на днях перепроходить буду можешь добавиться в дискорде - МОЖЕМ ПАВТАРИТЬ!111!!#2257 Обычно я переписываю в цеттеле все конспекты, и буду переписывать темы из книги, сможем обсудить и порешать представленные там задачки.
@@newcomer3419 у тебя какой уровень джава
@@АлишерТоктомушев-щ7л Я не знаю как это замерить) Вообще прошел курс наиля на юдеми, сейчас вот перепройду книжку, затем java ee и за андроид разработку возьмусь, еще котлин нужен будет.
@@newcomer3419 база данных не будешь учить?я тоже хочу купить курс на юдеми
Подскажите почему int high - a.length - 1? Почему именно -1?
потому что индексирование начинается с 0, и не может быть меньше
Очень жаль, что нет продолжения курса, но та часть, что есть уже очень хороша, спасибо! Единственный вопрос со сложностью, согласен что осуществлять бинарный поиск гораздо быстрее, но он ведь работает только в отсортированном массиве. Получается что если у нас есть не отсортированный массив в котором нужно найти значение, нужно его сначала отсортировать. В итоге получаем сложность сортировки массива n*log(n) и после сортировки бинарный поиск у которого сложность log(n), так как n*log(n) хуже чем log(n) получаем конечную сложность этого алгоритма n*log(n), что ощутимо дольше при больших объемах данных чем поиск значения в не отсортированном массиве сложность которого равна О(n) и лучше в таких случаях использовать классический линейный поиск в не отсортированном массиве. Но конечно все еще зависит от того как дальше будут использоваться эти данные
Здравствуйте.
Видео хорошее, вполне всё понятно, плюс книжка "Грокаем алгоритмы" под боком, но возник вопрос, а каким образом бинарным поиском находят слово в словаре?
Потому что судя по той же книге и вашему видео я понял, что алгоритм перебирает только цифры... тем более логарифмическая функция
Скорее всего вы ответ уже знаете)) Но для тех, кто также задастся этим вопросом, то класс String имплементирует интерфейс Comparable, соответственно для сравниния нужно вызывать метод compareTo
а если нужно изначальный индекс найти, не отсортированный
спасибо помогло !
Рекурсивное решение от новичка:
public static int binarySearch (int[] arr, int number, int low, int high){
int middle=0;
middle=low+(high-low)/2;
if (number==arr[middle]){
return middle;
} else if (low==high){
return -1;
}else if (numberarr[middle]){
return binarySearch(arr,number,middle+1,high);
} else
return middle;
}
❤❤❤❤
Все встало на свои места, спасибо. Ну а как же быть тогда с поиском индекса , эта задача не менее интересна. И актуальна . Они будут рассмотрены ??
Бред 😤
Ура!!!
хорошее видео, я бы порекомендовал еще книжку "Грокаем алгоритмы" я ее проглатил за обе щеки за 3 вечера и самое главное, в моей тупой голове даже что-то отложилось
я конечно все понимаю, но не один человек на ютубе не обьясни, что делать если ключей в массиве несколько и надо подсчитать их колличество и вывести индексы
Создай массив для этих клучов и с помощью цикла поставь эти ключи. Вот так 👇
int[] keys = {3, 5, 7, 9};
for (int i = 0; i < keys.length; i++)
birnarySearch(здес массив, keys[i] );
Примерно так. Дальше сам делай
Чего бы не сделать еще и сортировку
Чего бы не посмотреть других авторов
@@ruslanvolovik2745 я что-то говорил про других авторов?
@@ssseoks ты же просил про сортировку, не судьба посмотреть видео других авторов. А я понял, тебе это принципиально
Ставь лайк если тоже только благодаря этому видео понял зачем нужны логарифмы
Сама же сортировка долгая -_-
Был бы признателен за видео о (Insertion/selection sort)
Их полно в ютубе или тебе принципиально
Жаль, что курс оказался незавершенным.
Индексы начинаются с ноля!
Наверно только узнал
@@ruslanvolovik2745 ??
буква мэ 🤣
slui.exe