Алгоритм бинарного/двоичного поиска. (Binary search algorithm)
HTML-код
- Опубликовано: 13 окт 2024
- В этом видео вы найдете реализацию алгоритма "Бинарный поиск", и так же его применение на нескольких примерах.
Группа ВК - windert0n
Twitch - / winderton
Twitter - / windert0n
Github - github.com/Win...
Есть реализация попроще:
Пусть 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.
Это било реально круто. Мне уже разказавали бинарний поиск , но я не знал даже что такое массив. Я вроде понял , но очень плохо(тогда). Первую функцию я понял сразу(потому что я её видел уже). С грубой силой тупил и пересмотрел и понял. Посмотря дважды видео , я очень рад , что я понял. Спасибо.
Немаловажный нюанс - бинарный поиск будет работать только на отсортированных/поиндексированных данных...
5:52
Об этом говорилось в видео
Не обязательно. Список может быть не отсортированый, но походу добавления в список новых значений надо сортировать
Передавать вектор по значению, а не по константной ссылке - это пиздец)
Больше памяти занимает и время исполнения немного больше)
молодец...и речь приятная, слушать легко.
прикольный пример использования алгоритма
Спасибо, очень познавательно.
Да круто,я его как рас спомнил и тут ты пронего рассказываешь cs50,
класс
Видео - ТОП! Спасибо огромное!
Спасибо за контент, с меня лайк и коммент. Удачи !
спасибо!
кстати, а если нужно найти минимальные значения массивов и потом количество минимальных элементов, как тогда быть?Это надо сначала найти минимальный элемент, без помощи бинарного поиска, а уже потом искать их количество с помощью бинарного поиска, или можно просто в бинарном поиске найти минимальный элемент, и там же его количество в массиве? прошу очень важно
алгоритм нахождение корня немного другой. во всяком случае я видел более грамотный подход в одной математической статейке где описывалось возведение в дробную степень.
epicilon:)
+1 Поржал)
Привет Win, а если вектор будет из 9 значений, то mid будет равен 4.5. Затем ты эти 4.5 передашь в индекс, то что будет тогда ?
Значение интовское, и округлится до 4
Привет бородач еще раз спасибо за то что ты делаешь. хотел спросить можно ли тебе задавать профессиональные вопросы и советоваться (не буду занозой) в коментах или где то еще?))))
А если сложить время/итерации затраченные на сортировку массива из 1 000 000 миллиона строк и бинарный поиск в нем, выигрыш все еще остается?
Было бы здорово если бы вы выложили код программ для детального анализа....я чайник еще
if (pow(ans, 2) == ans*ans) cout
На сколько итераций алгоритм Ньютона для вычисления кк. был бы тут эффективнее/не эффективнее?
Асимптотические сложности этих методов разные, метод бинарного поиска дал бы линейную сходимость(см вики) здесь, тк. на каждой итерации мы находим по сути ещё один значащий бит квадратного корня в двоичном представлении. Скорость сходимости в методе Ньютона зависит от величины шага в разностном приближении производной, если мы вычисляем её значение по разностной схеме. Так можно получить более быструю сходимость в смысле количества итераций, но здесь не учитывается разности во времени для выполнения одной итерации. Если мы берём аналитический вид, производной интересной нам функции, то можно ещё ускорить сходимость, вплоть до квадратичной, но проблема с ними в том, что возможна расходимость, при неудачном выборе начального приближения.
На практике даже если мы возьмем четверную точность, в котором на мантиссу отведено 112 бит, то метод двоичного поиска даст нам максимально точный ответ где-то за 112 с небольшим(потому что нужно знать ещё и порядок числа) итераций, но вообще копать этот вопрос можно до бесконечности.
Это всё применительно к данному уравнению. Ни метод Ньютона, ни метод дихотомии не гарантируют нахождения нулей для произвольных функций.
Спасибо за видео. Было бы круто прикреплять код из видео в описании под ним.
Я обычно так и делаю. Эти исходники тоже прикреплю.
Так а хдежишь описание линейного пути? Говорил выбирать его и не прогадаем :'(
Пожалуйста погромче звук записывайте
Да ждал когда ты закончешь. :-)
Когда ты говорил про линейный поиск, ты говорил про какой-то Эписилон, ты имел ввиду Эпсилон? en.wikipedia.org/wiki/Epsilon
Это долго объяснять, почему я Эпсилон называю "Эписилон", но да, я имел ввиду этот символ.
@@wndtn расскажешь? Немного жизнености преподавателя мотивирует учеников)
Бинарный квадратный корень для a
Разве добавление условия а ля if 0
Будет! Только нужно применять метод не напрямую к a
Получается бинарный поиск работает только в упорядоченных массивах?
Да, соответственно не понимаю как это связано с поиском слова в книге.
@@PurpleDaemon_ речь о телефонном справочнике..
epicilion - это пасхалка либо новая мода?
это буква греческого алфавита (только произносится она "эпсилон", не "эписилон")
спасибо
Какой микрофон используешь?
audio technica at2020
Благодарю
+Winderton есть ли в планах видео о работе с OGL, SDL и прочим?
SDL, GLFW будут. Вторая, точно будет. Я на ее основе буду движок делать, а c помощью SDL на С игру напишем.
Почему у тебя в бинарном поиске в 26 строке high = mid-1, на вики и в других источниках в этом месте high=mid. Насколько я понял, позапускав код, это приводит к лишней итерации. Поправь если не прав
Да, ты прав. Если ты положишь high = mid, то будешь лишний раз проверять условие для mid, хотя оно и проверено уже.
thank you
вычисляя корень из 100 получаю 9.999... эх
Спсб
К сожалению, я не понял смысл в цикле, в нахождении корня грубой силой.
он перебирает числа с определённым шагом, возводит их в квадрат и сравнивает с а
Смысл в том, чтобы показать, как много итераций требуется для нахождения корня таким лобовым методом и что это не оправдано. Ну и чтобы показать, насколько эффективен по сравнению с лобовым алгоритм дихотомии (бинарного поиска).
С++
Гууд
Это второй курс универа. Один из смыслов получить вышку.
Паша Захаров это уровень сложности девятый класс в школе .
В универе на втором курсе будете уже ООП во всю заниматься)
@@freedomtv2295 Я как ученик 9 класса, заявляю, то что это не правда )))Мы на Pascal'e ещё функции и массивы не начали проходить ))
Занимался ООП во всю на третьем курсе колледжа, полность согласен, то что в видео - уровень 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
какой язык программирования
с++
С--
Даже не знаю
А как сделать чтобы корректно работало, если в массиве есть повторяющиеся элементы? Или по плану бинарный поиск должен показывать только первый по счету элемент, даже если их два и больше
Бинарный поиск работает в отсортированном массиве, т.е. если нужно найти все числа "4", а их в массиве несколько, то массив имеет вид ... , 4, 4, 4, 4, 4, 4, ....
Наш бинарный поиск найдет одну из этих четверок, чтобы найти остальные, можно в циклу пройти вперед/назад по массиву и найти их все.
Или можно немного усложнить бинарный поиск. После того как он найдет четверку (например, найдет ... , 4, 4, 4, [4], 4, 4, .... ), после цикла while(low