Привет, стараюсь) Хочу создать самые понятные ролики на KZfaq, может со временем получится. При этом не хочется, чтоб блог скатился в очередной банальный обучающий курс, коих и так полон интернет) VK есть на главной странице.

Ключевой момент в том, что можно отсортировать данные один раз и в таком виде хранить. После этого можно постоянно использовать быстрый двоичный поиск. Так работают базы данных - для полей, по которым часто происходит поиск, строятся отсортированные индексы.

@@arhitutorials Спасибо за ответ. Еще вопрос: в результате мы решаем задачу проверки наличия искомого элемента в первичном массиве, а не его позиции как поставлена задача в 0:45, потому что мы получаем индекс элемента в отсортированном массиве, который никак не коррелирует с индексом этого же элемента в первичном массиве?

@@gessgess6186 Если надо найти индекс в первичном массиве, то можно составить массив из структур вида {элемент, его индекс в первичном массиве}, потом сортировать его по элементам. А потом искать в нем двоичным поиском. При нахождении структуры с элементом, находим так же и его оригинальный индекс. Так обычно и делают. Первичный массив не сортируют, а делают отдельный массив {значение, индекс} и уже с ним работают. Потому что обычно элементы имеют сложную структуру и искать часто надо по нескольким полям. Например, в массиве сотрудников можно искать и по фамилии и по номеру телефона, плюс там обычно куча других полей: адрес, должность, зарплата и т.д. Порядок при сортировке по фамилии и телефону будет разный. Чтоб не делать для поиска две копии массива, отсортированных по разным полям, делают так: массив оставляют как есть, а создают два новых массива {фамилия, индекс} и {телефон, индекс} и уже их сортируют и в них ищут. Найдя индекс берут полную запись по индексу из основного массива. Вот как-то так. По этому при проектировании базы данных хорошо бы заранее предусмотреть, по каким полям в таблице будет нужен поиск, чтоб построить для полей индексы.

@@arhitutorials Спасибо за исчерпывающий ответ и спасибо за ваш канал, желаю успехов в его дальнейшем развитии.

Да, правильно. Причем логарифм будет по основанию 2, если массив делится пополам. То есть для двоичного поиска в массиве размером N понадобится не более log2(N) шагов для поиска любого элемента.

Для работы алгоритма не обязательно, чтоб опорный элемент для разделения выбирался четко по середине массива. По этому любой массив можно сортировать. Другое дело, что для любого разделения можно придумать неудачный массив, на котором производительность просядет до n^2. Это недостаток данной сортировки.

@@arhitutorials не совсем понял про сложность О(n^2) для бинарного поиска... Ведь если массив отсортирован, то поиск всегда будет по О(log по основанию 2 от n). Ну а если не отсортирован, то учитывается худшая сложность для сортировки самого наилучшего способа "пирамидальный способ", у которой она равна О(N*LogN). Даже тогда сложность общая будет равна О(LogN+ NLogN), но никак не О(N^2)... Или что вы имели ввиду?

@@Chekist2008 Да, правильно. Сорри, я перепутал, не прочитал заголовок видео, подумал речь идет о быстрой сортировке. Хочу уточнить. Если массив не отсортирован, то линейный поиск за O(N). Если отсортировать, то используем бинарный поиск за log(N), да. Но так как сортировка выполняется только один раз, а искать потом можно сколько угодно, то я бы не стал складывать время сортировки и время поиска. Еще в некоторых случаях отсортировать массив можно за O(N), например используя поразрядную сортировку, или сортировку подсчетом. Скоро сделаю про это видео.

@@arhitutorials Спасибо огромное, теперь все понятно

Так это ж эквивалентные выражения (start + end) / 2 = start + (end - start)/2 то есть просто немного в другой форме записано то же самое. Может я думал о длине массива, когда писал. То есть middle - это start + пол длины подмассива.

Это IntelliJ IDEA community edition, можно скачать бесплатно без смс)

@@arhitutorials благодарю

Итак, исходное выражение: mid = low + ((high - low) / 2) умножаем все на 2, получаем: 2 * mid = 2 * low + high - low вычитаем 2 * low - low, получаем: 2 * mid = low + high теперь выражаем mid: mid = (low + high) / 2 таким образом: mid = low + ((high - low) / 2) это то же самое, что mid = (low + high) / 2 выражения эквивалентны, все верно.