Лучший алгоритм поиска // Vital Math 

А теперь давайте разберёмся с такой "мелочью" как сортировка 😏

лучший вид поиска это удалить половину,а потом всё остальное

Бинарный поиск был крайне популярен в стародавние воемена, когда гирлянды делали из большого количества последовательно включённых лампочек. Рано или поздно происходила потеря контакта или сгорала лампочка. Вот и делили пополам, потом прозванивали произвольно выбранную часть. Каждая итерация позволяла очень быстро найти неисправность. Дошёл до этого своими мозгами еще в детстве.

Я как программист скажу, что не все так однозначно. ) Двоичный поиск обычно работает с массивами. Т.е. все значения расположены в памяти подряд. Добавление нового элемента в такой массив это дорогая и долгая операция. Если нужно не только искать, но и часто изменять данные, то программисты используют красно-черное дерево или b+ дерево. Причем, алгоритм красно-черного дерева напишут без подсказки меньше 1% программистов. Потому что мало кто задумывался, как оно вообще работает. Это прямо магия какая то.

5:50 ролик начинается отсюда

Всегда рад видеть твоё видео!

Прекрасное видео. Спасибо большое, удачи Вам и успехов.

Любимая рубрика! Всегда эти видео оставляю на утро выходного дня, когда можно расслабленно посмотреть под чаек )

Было бы неплохо так ясно и понятно (этого не отнять) послушать по "магию" помехоустойчивого кодирования - коды Рида-Соломона. Отличный стык математики и IT и тоже классика еще из 60х. Но это чуть посложнее чем "детишки, просто делите все пополам"

Отличный ролик! Может, стоит задуматься о серии роликов про интересные алгоритмы?

Спасибо Вам за ролик

.бинарный поиск, анекдот: Начальник принес стопку анкет помощнику, чтоб он выбрал 10 кандидатов. Ушёл. Пришёл через час, помощник ещё возится с анкетами. Говорит, давай, я сам. Большую часть анкет убрал в сторону, не глядя, из оставшихся 15 выбрал 10 анкет. Помощник спросил, а как же стопка анкет, просмотреть, выбрать лучших. Начальник ответил, зачем нам неудачники... 😂😢

Ура, видео, в котором я хоть что-то понимаю

Программисты нажали F, чтобы отдать честь

С малолетства засиживался в библиотеках и поражался, как библиотекари ищут книгу. У одних сортировка по авторам, у других по названию, по жанру и тд. Потом узнал, что на каждую книгу десятка два карточек по критерию книги. Отсюда вывод - если есть возможность массив сортируй по мере наполнения, чтобы не было мучительно больно.

Спасибо, бро. может втолкуешь еще как работает алгоритм блюма?

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

Бинарный поиск в инженерии: при поломке, делим цепь на 2, проверяем работоспособность, продолжаем пока не найдем неисправный узел

Недавно решил разобраться с этим алгоритмом, я поражен его эффективностью. Спасибо за столь познавательный ролик!

Хотелось бы ещё видео про R-деревья и поиск среди пространственных данных.

Ура, я так рад что у тебя реклама появилась )

оказывается метод Коши программисты называют бинарным поиском! ))

мой любимый алгоритм

Обычно в программировании используют именно хэш-таблицы за счёт поиска за O(1) и добавления элемента за амортизированное O(1). Если только не нужно выполнить нестрогий поиск слева/справа или не используются иммутабельные структуры данных.

в АЦП последовательного приближения тоже используется алгоритм бинарного поиска

Поиск, это, конечно, хорошо, но как на счёт сортировки самих массивов перед этим?)

Прямой доступ по указателю ещё быстрее) )

Виталий, -> 8:20 : у тебя ошибка в 8 строчке кода (array не определена, не забываем про регистр ;-) )

Интересно, а в Пайтоне есть поиск для неоднородного массива, заполненного неотсортированными данными? В Julia например есть!

Обманчиво простая штука.

Как всегда захватывающе. F

У бинарного поиска один огромный минус - требуется предварительная сортировка массива. Редко исходный массив остается неизменным. Значит после каждого изменения требуется сортировка, а это очень наклАдная операция.

держи, может придется где то + или -1 поставить, а может и нет....))) не оптимизировано типа i++ и тд для понимания, да и компилятор оптимизирует сам, главное писать понятно...))) =================================================================== xx = искомое значение. dd = length(mas); //начальная длина массива. =================================================================== // для ориентации // int bg =0; //начало массива. // для ориентации // int en = dd; //конец массива. int sm = 0; //смещение в массиве. while (zz != xx ) //выполнять до тех пор пока не равенство. { ii = dd div 2; //половина целое, край. zz = mas[ ii + sm ] ;//беру крайнее значение у первой половины. sm=ii+sm; if (sm == 1) { std::cout

О! Вы еще и в проге разбираетесь))

А чем подобный "бинарный поиск" отличается от метода последовательного приближения применяемого в АЦП, где как такового упорядочивания исходных данных нет (вернее исходные данные не извести и/или могут быть изменяемые со временем)?

8:04 в python на строки делить не принято ;) комментарии там через решетку

14:25 Пасхалочка :-)

Метод половинного деления, неосознанно применялся еще в школе, особенно когда пошли толстые учебники. И на слова учителя " открываем учебник на 68 странице", что-то не припомню, что бы листали подряд страницы. Тупо делили пополам, пополам и т.д.

Помню, в детстве писал на ассемблере код для функций умножения и деления целых чисел. Умножение реализовал как цикл суммирования. Деление - как поиск значения обратной функции от умножения, как раз методом дихотомии...

По-моему, самый простой способ написать бп - это использовать полуинтервалы, то есть: Индексы элементов массива это числа от 0 до n-1(n - длина массива, пусть l=0 - указатель на начало, r=n - указатель на конец(не включает последний элемент массива), если r - l == 1, то такой полуинтервал включает в себя один элемент - искомый(если он есть в массиве) while r > l + 1: m = (r + l) / 2 if array[m] > value: r = m else: l = m if array[l] == value: return l else: return -1 Никаких +-1, и проверка на равенство необязательна

Когда то давно я изобрел этот метод. Но потом оказалось, что кто-то уже давно изобрел его до меня. 😅😢😂 сейчас у меня есть изобретение в области ии, которое позволит ии понимать динамические образы, надеюсь хоть тут успею быть первым😊

Всего-то осталось предварительно отсортировать массив. И можно применять бинарный поиск ))

Еще не досмотрел. 0:45. Понятно, что это пример, но в случае с книгами я бы предпочел алгоритм, который выбирал бы полки с краю, если книга, например, начинается на А. Как мы обычно ищем слово в словаре? Мы хотим найти слово на букву И (10-я), например. Мы понимаем, что это ближе к началу и открываем примерно в первой трети словаря. Пусть там К (12-я). Значит И левее, но не намного. Примерно 0,8. Переходим туда и видим Е. Значит И где-то посередине. Делим оставшиеся страницы пополам и попадаем на И. По-моему, это даже какой-то реальный алгоритм с названием, но не помню точно, как называется. Если найду, отпишу UPDATE: похоже на интерполяционный поиск

Можно было и про quick-sort упомянуть. Удивительно быстро сортирует массив, в котором потом ищем. Тоже делит пополам, правда там рекурсия а это чуть посложнее для понимания

37 не случайно?

Две самые популярные ошибки - это ошибка границы (она же - ошибка плюс-минус-единицы). Если вы понимаете, о чём я.

Обратное геометрической прогрессии?

8:35 а как код себя поведет, если объектов в массиве нечетное число? Середина будет дробной, ее же надо к int приводить, тогда как раз серединой станет меньший элемент

На самом деле, лексикографическое упорядочение - это древесная структура данных: первый знак #х, второй знак #у и т.д. Соответственно и момент выяснения, в каком месте находится "середина диапазона" по отношению к искомому номеру - это тоже сравнение внутри дерева. Тогда нафига проверять в дальнейшем те ветви, которые уже заведомо отвергнуты на предыдущей проверке??? То есть - древесная структура данных однозначно диктует древесный поиск в качесве бвстрейшего!☝️ Бинарный алгоритм хорош при поиске в линейно упорядоченном массиве - например на этапе выяснения, какая из N букв стоит на следующей позиции. И тогда возникает вопрос: скольки буквенным алфавитом следует пользоваться, чтобы в итоге быстрее найти нужный объект из N? Боюсь соврать, но по-моему ответ "е" 😊

2 года назад пытался написать бинарное дерево на С++. Только когда закончил понял, что криво всё сделал, и этим неудобно пользоваться. Потом стало лень исправлять. Так, что не буду это безобразие никому отправлять. Ради ваших нервных клеток)

А как быть если элемент не найден и ты хочешь получить не -1, а индекс элемента для вставки нового(т.е. ненайденого) элемента? Это помогло бы иметь всегда отсортированную последовательность.

Я щас учусь в 11 классе, в этом году прошёл на всерос по инфе. Могу смело сказать, что всех людей, косячащих в такой халяве, как бинок, надо уволить нафиг

Бинарный поиск легко может как найти нужное число, так и обратная задача: добавление 1 элемента в массив.

Это не комментарий , а вопрос. Если понимать натуральный ряд как последовательность чисел, в которой два соседних числа находятся на одинаковом расстоянии, то это расстояние может быть рациональным числом , иррациональным (для нечетных оснований) и даже трансцендентных чисел (например, точки , определяемые трансцендентной функцией синус)?

Гениально. Сначала мы долго и мучительно отсортируем миллиард записей, а потом быстро найдём нужную :) Дело не в методе поиска, а в отсортированности данных.

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

Только честно, вы 37 расположили на превью после видео Veritasium?

13:43 в 10-й строке пропущена точка с запятой, в этом ошибка?

8:25 А если искомое число -1 , то при выводе -1 мы какой вывод должны сделать: что ответ -1 ,или что искомого числа нет?😂

-Этот алгоритм легкий разберется даже ребенок -В нем ошибаются 90% программистов ок...

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

Вот сортировка как раз очень длительный и утомительный процесс с многократной перестановкой элементов. Кстати, вопросик: а ошибки у программистов в программе поиска были такие стандартные, о которых рассказывал автор видоса? Типа, переполнение промежуточного значения и неверное условие границ отсева... И возврата... Или есть еще какие-то подводные камни в трех -соснах- строках кода?

Где отсортированы все решения проблем, чтобы искать их с помощью бинарного поиска?

А как в неупорядоченном массиве искать?

Не работает этот метод. Как найти одну единственную среди массива подруг? Получается только линейным методом перебора😊

а вот я бы еще такой вопрос задал: а какой смысл писать код бинарного поиска, если он уже есть? на том же Python есть bisect. крайне маловероятно, что свой код будет работать лучше, чем всеми используемые реализации, т.е. пользоваться им даже ты сам/сама не будешь. понимания принципа работы поиска едва ли станет больше. а особенности языка, распределения памяти, переполнения и пр. и так встретятся при постоянном кодинге. а если кодишь не постоянно, то с этими проблемами тем более нет смысла возиться: есть рабочий проверенный вариант - берешь его, адаптируешь для своих нужд и используешь

Дональд Кнут, стрелочная нотация-это его?

Двадцать пять лет тому назад, я поручил бинарному поиску найти смысл жизни, а он, редиска, до сих пор ищет. При этом, он умудрился пережить двух кошек, одну собаку, три аквариума с рыбками, бесчисленное количество кактусов и тараканов, причём не только тех тараканов, которые живут за печкой, но и в разных головах. ;-) Ну это всё шутки юмора, а теперь о серьёзном: этот комментарий 227-ой, а это простое число! ;-)

А еще интересно, почему Виталий для примера выбрал число 37...? :) ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-d6iQrh2TK98.html&ab_channel=Veritasium

15:00

В коде ошибка: return mid. При этом выше в коде Mid

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

Лучший способ поиска - ничего не терять😊

Только алгоритм, по-моему, тернарный (где бинарность - частный случай: для четного числа элементов в массиве).

Я такой алгоритм классе в 8ом как хобби в школе сам придумал написав его без ошибок, я могу считаться гением?🤣

Да, бинарный поиск - это очевидное решение для упорядоченных массивов. Вот бы было что-то подобное для НЕупорядоченных!

1. Бинарный поиск это, конечно, хорошо. Но если есть возможность пользоваться знанием того, какое распределение, то есть более эффективные алгоритмы. В нерперывном случае для поиска нуля монотонной гладкой функции (что по сути та же задача) обычно применим метод Ньютона, который обходит дихотомию как сокол черепаху. В дискретном случае иногда также получается воспользоваться структурой набора данных. 2. 7:40. "//" в Рython для комментариев не используется (используется "#") 3. Каждый раз, когда слышу "для хеш-таблиц среднее время поиска - константа" тяжело вздыхаю. Не то чтобы это совсем неправда, но есть достаточно много случаев, когда это ломается. 4. Написать без ошибок код бинарного поиска вполне можно. Но это такой челлендж для занудных зануд - глаз должен быть намётан на подобные ошибки.

На Python: import numpy as np import time # Генерация массива из 100 тыс. чисел без повторений data = np.random.choice(np.arange(1, 10000000), size=999999, replace=False) # Вывод массива #print(data) def binary_search(arr, target): left, right = 0, len(arr) - 1 start_time = time.time() while left target: right = mid - 1 # Если искомый элемент больше значения в середине, # продолжаем поиск в правой половине списка else: left = mid + 1 # Если элемент не найден, возвращаем -1 end_time = time.time() print(f"Время поиска: {end_time - start_time} секунд") return -1 # Искомый элемент, например target = 69248 # Вызов функции бинарного поиска index = binary_search(data, target) if index != -1: print(f"Элемент {target} найден в позиции {index}.") else: print(f"Элемент {target} не найден.") Но увеличьте размерность массива data еще на 2 разряда, и ваша ОЗУ компьютера скажет вам до свидания.

Есть ещё и адаптивный поиск. Пример: если вы ищете в справочнике слово на букву Ф вы же не лезете в середину справочника. Вы лезете ближе к концу.

return -1 в пайтоне совершенно необязательно, так что это даже 11-строчный алгоритм.

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-zWyPZUe1VcE.html тоже косяк У L+R не будет на 3 цифры больше. Максимум на 1

Сортировка сравнением ограничение по временной сложности nlogn именно из-за логарифм поиска… этот самый логарифм поиска многим Математикам не давал покоя… так появились деревья

Переполнение целых чисел? Со времён ухода с 8-битных процессоров не слышал про такое.

Как правильно заходить в библиотеку 😅 Надо сразу подойти к библиотекарю и поздороваться. Сразу спроси есть ли долги и отдай книги которые брал ранее. Только после этого проси новые!

1:00 1) увидел код, но не успел рассмотреть 2) перемотал назад чтобы рассмотреть 3) понял что не знаешь какой это язык 4) смотришь дальше

Полинарный поиск круче, если использовать распараллеливание.

а гугл как ищет?

0:55 - властвуй, от слова "власть".

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-zWyPZUe1VcE.html 77=71... Кто ещё заметил?

Лучше было бы тогда указать индексацию с нуля

Ты не забывай, что когда ты просишь отправить код, указывать среду для его выполнения!!! Я как раз таки отправил для VS Code, ну а в REPL без конструкции begin и end просто не обойтись!!!)))

Не знал что 77 = 71 9:31

Старый анекдот про "как найти льва в пустыне?" =)

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

Больцано и Коши: бисекция рулит! Ньютон: алё, мы же всё ещё говорим про математику? Метод имени меня не хотите ли? Это к тому, что бинарный поиск - не лучший. Он лучший из худших, когда природа хранимых и искомых данных не позволяет ничего больше, чем ввести отношение порядка. Даже в библиотеке никто не занимается такой фигнёй, как бисектить по стеллажам (и получать гигантские кешмиссы для произвольного доступа и гигантские задержки для последовательного - бегать от стеллажа к стеллажу). Вместо этого берут индекс. И это, кстати, довольно близко по идеям к методам второго порядка.

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

Фигасе

Я зашёл сюда только что бы поставить лайк за число 37 на превью. Слава Иваново

Вот только он работает исключительно в отсортированных массивах

А слабо рассказать про алгоритм Гровера?