наконец-то простое и понятное объяснение реализации алгоритма, спасибо автору

Есть реализация попроще: Пусть l - левая граница, r - правая, m - середина, x - искомое число: while(r-l>1){ m = (l+r)/2; m>=x? r = m : l = m; } cout

Спасибо, очень познавательно.

Видео - ТОП! Спасибо огромное!

Это било реально круто. Мне уже разказавали бинарний поиск , но я не знал даже что такое массив. Я вроде понял , но очень плохо(тогда). Первую функцию я понял сразу(потому что я её видел уже). С грубой силой тупил и пересмотрел и понял. Посмотря дважды видео , я очень рад , что я понял. Спасибо.

Спасибо за контент, с меня лайк и коммент. Удачи !

Да круто,я его как рас спомнил и тут ты пронего рассказываешь cs50, класс

молодец...и речь приятная, слушать легко.

прикольный пример использования алгоритма

В строке "int mid = (low + high) / 2;" правильнее писать "int mid = low + (high - low) / 2;". Поскольку при огромном количестве элементов в массиве numbers возможно переполнение индекса mid.

Привет бородач еще раз спасибо за то что ты делаешь. хотел спросить можно ли тебе задавать профессиональные вопросы и советоваться (не буду занозой) в коментах или где то еще?))))

Да ждал когда ты закончешь. :-)

epicilon:)

@izualno_oname7234

5 жыл бұрын

+1 Поржал)

кстати, а если нужно найти минимальные значения массивов и потом количество минимальных элементов, как тогда быть?Это надо сначала найти минимальный элемент, без помощи бинарного поиска, а уже потом искать их количество с помощью бинарного поиска, или можно просто в бинарном поиске найти минимальный элемент, и там же его количество в массиве? прошу очень важно

Немаловажный нюанс - бинарный поиск будет работать только на отсортированных/поиндексированных данных...

@yehorpidhornyi9999

7 жыл бұрын

5:52

@Fovaxus

5 жыл бұрын

Об этом говорилось в видео

@_l.e.n.y_4956

2 жыл бұрын

Не обязательно. Список может быть не отсортированый, но походу добавления в список новых значений надо сортировать

Передавать вектор по значению, а не по константной ссылке - это пиздец)

@user-gv1zx8cq4l

5 жыл бұрын

Больше памяти занимает и время исполнения немного больше)

спасибо!

thank you

Спасибо за видео. Было бы круто прикреплять код из видео в описании под ним.

@wndtn

7 жыл бұрын

Я обычно так и делаю. Эти исходники тоже прикреплю.

спасибо

Привет Win, а если вектор будет из 9 значений, то mid будет равен 4.5. Затем ты эти 4.5 передашь в индекс, то что будет тогда ?

@dm3y434

5 жыл бұрын

Значение интовское, и округлится до 4

А как сделать чтобы корректно работало, если в массиве есть повторяющиеся элементы? Или по плану бинарный поиск должен показывать только первый по счету элемент, даже если их два и больше

@4AneR

7 жыл бұрын

Бинарный поиск работает в отсортированном массиве, т.е. если нужно найти все числа "4", а их в массиве несколько, то массив имеет вид ... , 4, 4, 4, 4, 4, 4, .... Наш бинарный поиск найдет одну из этих четверок, чтобы найти остальные, можно в циклу пройти вперед/назад по массиву и найти их все. Или можно немного усложнить бинарный поиск. После того как он найдет четверку (например, найдет ... , 4, 4, 4, [4], 4, 4, .... ), после цикла while(low

На сколько итераций алгоритм Ньютона для вычисления кк. был бы тут эффективнее/не эффективнее?

@DiamondSane

7 жыл бұрын

Асимптотические сложности этих методов разные, метод бинарного поиска дал бы линейную сходимость(см вики) здесь, тк. на каждой итерации мы находим по сути ещё один значащий бит квадратного корня в двоичном представлении. Скорость сходимости в методе Ньютона зависит от величины шага в разностном приближении производной, если мы вычисляем её значение по разностной схеме. Так можно получить более быструю сходимость в смысле количества итераций, но здесь не учитывается разности во времени для выполнения одной итерации. Если мы берём аналитический вид, производной интересной нам функции, то можно ещё ускорить сходимость, вплоть до квадратичной, но проблема с ними в том, что возможна расходимость, при неудачном выборе начального приближения. На практике даже если мы возьмем четверную точность, в котором на мантиссу отведено 112 бит, то метод двоичного поиска даст нам максимально точный ответ где-то за 112 с небольшим(потому что нужно знать ещё и порядок числа) итераций, но вообще копать этот вопрос можно до бесконечности. Это всё применительно к данному уравнению. Ни метод Ньютона, ни метод дихотомии не гарантируют нахождения нулей для произвольных функций.

Какой микрофон используешь?

@wndtn

7 жыл бұрын

audio technica at2020

@evan_ry

7 жыл бұрын

Благодарю

@tagil1234567

7 жыл бұрын

+Winderton есть ли в планах видео о работе с OGL, SDL и прочим?

@wndtn

7 жыл бұрын

SDL, GLFW будут. Вторая, точно будет. Я на ее основе буду движок делать, а c помощью SDL на С игру напишем.

Гууд

А если сложить время/итерации затраченные на сортировку массива из 1 000 000 миллиона строк и бинарный поиск в нем, выигрыш все еще остается?

Спсб

Когда ты говорил про линейный поиск, ты говорил про какой-то Эписилон, ты имел ввиду Эпсилон? en.wikipedia.org/wiki/Epsilon

@wndtn

7 жыл бұрын

Это долго объяснять, почему я Эпсилон называю "Эписилон", но да, я имел ввиду этот символ.

@user-ll2sn8rs3c

4 жыл бұрын

@@wndtn расскажешь? Немного жизнености преподавателя мотивирует учеников)

Было бы здорово если бы вы выложили код программ для детального анализа....я чайник еще

Так а хдежишь описание линейного пути? Говорил выбирать его и не прогадаем :'(

epicilion - это пасхалка либо новая мода?

@bespelotnik1950

6 жыл бұрын

это буква греческого алфавита (только произносится она "эпсилон", не "эписилон")

Почему у тебя в бинарном поиске в 26 строке high = mid-1, на вики и в других источниках в этом месте high=mid. Насколько я понял, позапускав код, это приводит к лишней итерации. Поправь если не прав

@cybelash5231

5 жыл бұрын

Да, ты прав. Если ты положишь high = mid, то будешь лишний раз проверять условие для mid, хотя оно и проверено уже.

Получается бинарный поиск работает только в упорядоченных массивах?

@PurpleDaemon_

4 жыл бұрын

Да, соответственно не понимаю как это связано с поиском слова в книге.

@user-ml4ec8bf9w

4 жыл бұрын

@@PurpleDaemon_ речь о телефонном справочнике..

алгоритм нахождение корня немного другой. во всяком случае я видел более грамотный подход в одной математической статейке где описывалось возведение в дробную степень.

Ссылку бы

if (pow(ans, 2) == ans*ans) cout

Пожалуйста погромче звук записывайте

Бинарный квадратный корень для a

@funnyh0rr0r31

5 жыл бұрын

Разве добавление условия а ля if 0

@cybelash5231

5 жыл бұрын

Будет! Только нужно применять метод не напрямую к a

С++

К сожалению, я не понял смысл в цикле, в нахождении корня грубой силой.

@Wi1dLife

7 жыл бұрын

он перебирает числа с определённым шагом, возводит их в квадрат и сравнивает с а

@cybelash5231

5 жыл бұрын

Смысл в том, чтобы показать, как много итераций требуется для нахождения корня таким лобовым методом и что это не оправдано. Ну и чтобы показать, насколько эффективен по сравнению с лобовым алгоритм дихотомии (бинарного поиска).

Это второй курс универа. Один из смыслов получить вышку.

@freedomtv2295

6 жыл бұрын

Паша Захаров это уровень сложности девятый класс в школе . В универе на втором курсе будете уже ООП во всю заниматься)

@kayman3415

5 жыл бұрын

@@freedomtv2295 Я как ученик 9 класса, заявляю, то что это не правда )))Мы на Pascal'e ещё функции и массивы не начали проходить ))

@Nickell.

5 жыл бұрын

Занимался ООП во всю на третьем курсе колледжа, полность согласен, то что в видео - уровень 9-11 класса. Только вот они там это проходить не будут, там это не надо.

Отличный пример конченного использования маджик намберов

вычисляя корень из 100 получаю 9.999... эх

Это матиматика, "метод половинного деления"

@cybelash5231

5 жыл бұрын

Хоть горшком назови

какой язык программирования

@dimonidze

6 жыл бұрын

с++

@ruslanvolovik2745

4 жыл бұрын

С--

@ruslanvolovik2745

4 жыл бұрын

Даже не знаю

Ну на черной теме так плохо видно на маленьком ноутбуке, неужели вы не просматриваете свое видео? на работе не могу во весь экран смотреть, а на маленьком не видно, поэтому дизлайк.

Странный пример с книгой и именем

@phskr

5 жыл бұрын

Я думаю, он имел ввиду словарь.

реализация бинарного поиска - хуйня. попробуй нулевой массив передать, например

@johnashley5960

5 жыл бұрын

template // вектор сука разный может быть, с разным аллокатором, например T *binary(const V &n, T x) { // вектор по ссылке сука size_t first, last, mid; first = 0; last = n.size(); //никаких ноль минус один сука, никаких интежер оверфлоу while (first mid = first + (last-first)/2; // никаких сука я сказал if (x last = mid; } else if (x > n[mid]) { first = mid + 1; } else { return const_cast(&n[mid]); // и возвращаем блять указатель, а не найдено/не найдено } } return nullptr; } и не надо ебаться с итераторами у контейнера, они в данном случае замедляют поиск выкладываю, потому что полно ебанутых реализаций (таких как твоя) и заебало ловить сегфолты в говноприложениях

@johnashley5960

5 жыл бұрын

и нахуя оно выдаёт true или false? можно тот же стл использовать для этого. алгоритм выше для того, что бы обойти ограничение, вызванное предикатом, в функции lower_bound