Это било реально круто. Мне уже разказавали бинарний поиск , но я не знал даже что такое массив. Я вроде понял , но очень плохо(тогда). Первую функцию я понял сразу(потому что я её видел уже). С грубой силой тупил и пересмотрел и понял. Посмотря дважды видео , я очень рад , что я понял. Спасибо.
В строке "int mid = (low + high) / 2;" правильнее писать "int mid = low + (high - low) / 2;". Поскольку при огромном количестве элементов в массиве numbers возможно переполнение индекса mid.
кстати, а если нужно найти минимальные значения массивов и потом количество минимальных элементов, как тогда быть?Это надо сначала найти минимальный элемент, без помощи бинарного поиска, а уже потом искать их количество с помощью бинарного поиска, или можно просто в бинарном поиске найти минимальный элемент, и там же его количество в массиве? прошу очень важно
Асимптотические сложности этих методов разные, метод бинарного поиска дал бы линейную сходимость(см вики) здесь, тк. на каждой итерации мы находим по сути ещё один значащий бит квадратного корня в двоичном представлении. Скорость сходимости в методе Ньютона зависит от величины шага в разностном приближении производной, если мы вычисляем её значение по разностной схеме. Так можно получить более быструю сходимость в смысле количества итераций, но здесь не учитывается разности во времени для выполнения одной итерации. Если мы берём аналитический вид, производной интересной нам функции, то можно ещё ускорить сходимость, вплоть до квадратичной, но проблема с ними в том, что возможна расходимость, при неудачном выборе начального приближения. На практике даже если мы возьмем четверную точность, в котором на мантиссу отведено 112 бит, то метод двоичного поиска даст нам максимально точный ответ где-то за 112 с небольшим(потому что нужно знать ещё и порядок числа) итераций, но вообще копать этот вопрос можно до бесконечности. Это всё применительно к данному уравнению. Ни метод Ньютона, ни метод дихотомии не гарантируют нахождения нулей для произвольных функций.
Привет бородач еще раз спасибо за то что ты делаешь. хотел спросить можно ли тебе задавать профессиональные вопросы и советоваться (не буду занозой) в коментах или где то еще?))))
алгоритм нахождение корня немного другой. во всяком случае я видел более грамотный подход в одной математической статейке где описывалось возведение в дробную степень.
Смысл в том, чтобы показать, как много итераций требуется для нахождения корня таким лобовым методом и что это не оправдано. Ну и чтобы показать, насколько эффективен по сравнению с лобовым алгоритм дихотомии (бинарного поиска).
Почему у тебя в бинарном поиске в 26 строке high = mid-1, на вики и в других источниках в этом месте high=mid. Насколько я понял, позапускав код, это приводит к лишней итерации. Поправь если не прав
Занимался ООП во всю на третьем курсе колледжа, полность согласен, то что в видео - уровень 9-11 класса. Только вот они там это проходить не будут, там это не надо.
Ну на черной теме так плохо видно на маленьком ноутбуке, неужели вы не просматриваете свое видео? на работе не могу во весь экран смотреть, а на маленьком не видно, поэтому дизлайк.
template // вектор сука разный может быть, с разным аллокатором, например T *binary(const V &n, T x) { // вектор по ссылке сука size_t first, last, mid; first = 0; last = n.size(); //никаких ноль минус один сука, никаких интежер оверфлоу while (first < last) { mid = first + (last-first)/2; // никаких сука я сказал if (x < n[mid]) { last = mid; } else if (x > n[mid]) { first = mid + 1; } else { return const_cast(&n[mid]); // и возвращаем блять указатель, а не найдено/не найдено } } return nullptr; } и не надо ебаться с итераторами у контейнера, они в данном случае замедляют поиск выкладываю, потому что полно ебанутых реализаций (таких как твоя) и заебало ловить сегфолты в говноприложениях
и нахуя оно выдаёт true или false? можно тот же стл использовать для этого. алгоритм выше для того, что бы обойти ограничение, вызванное предикатом, в функции lower_bound
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
наконец-то простое и понятное объяснение реализации алгоритма, спасибо автору
Есть реализация попроще:
Пусть l - левая граница, r - правая, m - середина, x - искомое число:
while(r-l>1){
m = (l+r)/2;
m>=x? r = m : l = m;
}
cout
Это било реально круто. Мне уже разказавали бинарний поиск , но я не знал даже что такое массив. Я вроде понял , но очень плохо(тогда). Первую функцию я понял сразу(потому что я её видел уже). С грубой силой тупил и пересмотрел и понял. Посмотря дважды видео , я очень рад , что я понял. Спасибо.
В строке "int mid = (low + high) / 2;" правильнее писать "int mid = low + (high - low) / 2;". Поскольку при огромном количестве элементов в массиве numbers возможно переполнение индекса mid.
молодец...и речь приятная, слушать легко.
прикольный пример использования алгоритма
Спасибо, очень познавательно.
Да круто,я его как рас спомнил и тут ты пронего рассказываешь cs50,
класс
Спасибо за контент, с меня лайк и коммент. Удачи !
Видео - ТОП! Спасибо огромное!
Передавать вектор по значению, а не по константной ссылке - это пиздец)
Больше памяти занимает и время исполнения немного больше)
А если сложить время/итерации затраченные на сортировку массива из 1 000 000 миллиона строк и бинарный поиск в нем, выигрыш все еще остается?
кстати, а если нужно найти минимальные значения массивов и потом количество минимальных элементов, как тогда быть?Это надо сначала найти минимальный элемент, без помощи бинарного поиска, а уже потом искать их количество с помощью бинарного поиска, или можно просто в бинарном поиске найти минимальный элемент, и там же его количество в массиве? прошу очень важно
Немаловажный нюанс - бинарный поиск будет работать только на отсортированных/поиндексированных данных...
5:52
Об этом говорилось в видео
Не обязательно. Список может быть не отсортированый, но походу добавления в список новых значений надо сортировать
epicilon:)
+1 Поржал)
Так а хдежишь описание линейного пути? Говорил выбирать его и не прогадаем :'(
Да ждал когда ты закончешь. :-)
На сколько итераций алгоритм Ньютона для вычисления кк. был бы тут эффективнее/не эффективнее?
Асимптотические сложности этих методов разные, метод бинарного поиска дал бы линейную сходимость(см вики) здесь, тк. на каждой итерации мы находим по сути ещё один значащий бит квадратного корня в двоичном представлении. Скорость сходимости в методе Ньютона зависит от величины шага в разностном приближении производной, если мы вычисляем её значение по разностной схеме. Так можно получить более быструю сходимость в смысле количества итераций, но здесь не учитывается разности во времени для выполнения одной итерации. Если мы берём аналитический вид, производной интересной нам функции, то можно ещё ускорить сходимость, вплоть до квадратичной, но проблема с ними в том, что возможна расходимость, при неудачном выборе начального приближения.
На практике даже если мы возьмем четверную точность, в котором на мантиссу отведено 112 бит, то метод двоичного поиска даст нам максимально точный ответ где-то за 112 с небольшим(потому что нужно знать ещё и порядок числа) итераций, но вообще копать этот вопрос можно до бесконечности.
Это всё применительно к данному уравнению. Ни метод Ньютона, ни метод дихотомии не гарантируют нахождения нулей для произвольных функций.
спасибо!
Привет Win, а если вектор будет из 9 значений, то mid будет равен 4.5. Затем ты эти 4.5 передашь в индекс, то что будет тогда ?
Значение интовское, и округлится до 4
Привет бородач еще раз спасибо за то что ты делаешь. хотел спросить можно ли тебе задавать профессиональные вопросы и советоваться (не буду занозой) в коментах или где то еще?))))
Было бы здорово если бы вы выложили код программ для детального анализа....я чайник еще
Когда ты говорил про линейный поиск, ты говорил про какой-то Эписилон, ты имел ввиду Эпсилон? en.wikipedia.org/wiki/Epsilon
Это долго объяснять, почему я Эпсилон называю "Эписилон", но да, я имел ввиду этот символ.
@@wndtn расскажешь? Немного жизнености преподавателя мотивирует учеников)
Спасибо за видео. Было бы круто прикреплять код из видео в описании под ним.
Я обычно так и делаю. Эти исходники тоже прикреплю.
Получается бинарный поиск работает только в упорядоченных массивах?
Да, соответственно не понимаю как это связано с поиском слова в книге.
@@PurpleDaemon_ речь о телефонном справочнике..
epicilion - это пасхалка либо новая мода?
это буква греческого алфавита (только произносится она "эпсилон", не "эписилон")
алгоритм нахождение корня немного другой. во всяком случае я видел более грамотный подход в одной математической статейке где описывалось возведение в дробную степень.
if (pow(ans, 2) == ans*ans) cout
Пожалуйста погромче звук записывайте
спасибо
Ссылку бы
Какой микрофон используешь?
audio technica at2020
Благодарю
+Winderton есть ли в планах видео о работе с OGL, SDL и прочим?
SDL, GLFW будут. Вторая, точно будет. Я на ее основе буду движок делать, а c помощью SDL на С игру напишем.
К сожалению, я не понял смысл в цикле, в нахождении корня грубой силой.
он перебирает числа с определённым шагом, возводит их в квадрат и сравнивает с а
Смысл в том, чтобы показать, как много итераций требуется для нахождения корня таким лобовым методом и что это не оправдано. Ну и чтобы показать, насколько эффективен по сравнению с лобовым алгоритм дихотомии (бинарного поиска).
thank you
Бинарный квадратный корень для a
Разве добавление условия а ля if 0
Будет! Только нужно применять метод не напрямую к a
Почему у тебя в бинарном поиске в 26 строке high = mid-1, на вики и в других источниках в этом месте high=mid. Насколько я понял, позапускав код, это приводит к лишней итерации. Поправь если не прав
Да, ты прав. Если ты положишь high = mid, то будешь лишний раз проверять условие для mid, хотя оно и проверено уже.
Спсб
Это второй курс универа. Один из смыслов получить вышку.
Паша Захаров это уровень сложности девятый класс в школе .
В универе на втором курсе будете уже ООП во всю заниматься)
@@freedomtv2295 Я как ученик 9 класса, заявляю, то что это не правда )))Мы на Pascal'e ещё функции и массивы не начали проходить ))
Занимался ООП во всю на третьем курсе колледжа, полность согласен, то что в видео - уровень 9-11 класса.
Только вот они там это проходить не будут, там это не надо.
вычисляя корень из 100 получаю 9.999... эх
Гууд
С++
какой язык программирования
с++
С--
Даже не знаю
Странный пример с книгой и именем
Это матиматика, "метод половинного деления"
Хоть горшком назови
Ну на черной теме так плохо видно на маленьком ноутбуке, неужели вы не просматриваете свое видео? на работе не могу во весь экран смотреть, а на маленьком не видно, поэтому дизлайк.
реализация бинарного поиска - хуйня. попробуй нулевой массив передать, например
template // вектор сука разный может быть, с разным аллокатором, например
T *binary(const V &n, T x) { // вектор по ссылке сука
size_t first, last, mid;
first = 0;
last = n.size(); //никаких ноль минус один сука, никаких интежер оверфлоу
while (first < last) {
mid = first + (last-first)/2; // никаких сука я сказал
if (x < n[mid]) {
last = mid;
} else if (x > n[mid]) {
first = mid + 1;
} else {
return const_cast(&n[mid]); // и возвращаем блять указатель, а не найдено/не найдено
}
}
return nullptr;
}
и не надо ебаться с итераторами у контейнера, они в данном случае замедляют поиск
выкладываю, потому что полно ебанутых реализаций (таких как твоя) и заебало ловить сегфолты в говноприложениях
и нахуя оно выдаёт true или false? можно тот же стл использовать для этого. алгоритм выше для того, что бы обойти ограничение, вызванное предикатом, в функции lower_bound