Кружок 1С #2. Двоичный поиск (бинарный, дихотомия) в 1С.

Разберем кейс поиска в упорядоченном массиве по алгоритму двоичного поиска в упорядоченном массиве, в нашем случае файле.
Статья на нашем сайте: softonit.ru/articles/1c/kruzh...
Условие задачи
Нужна возможность осуществлять анализ введенного пароля на то, что он скомпрометирован путем анализа файлов часто используемых паролей.
Итого: у нас есть введенный пользователем пароль, и нам необходимо путем перебора нескольких макетов с часто используемыми паролями, в которых на каждой строке введен пароль в нижнем регистре определить совпадает ли введенный пароль с тем, который ввел пользователь с теми паролями, которые есть в файле. Если он найден, надо написать, что пароль скомпрометирован. Обращаю внимание, что мы опускаем то, что регистр может быть другим. Будем введенную строку пользователя переводить в нижний регистр и проверять только маленькие буквы. Это упрощает задачу.
Первый вариант решения "в лоб"
В самом начале, я попытался использовать поиск "в лоб". Т.е. берем по очереди макеты с паролями и строчка, за строчкой сравниваем с тем, что ввел пользователь. Нашли - отлично, пароль скомпрометирован, если не нашли, то так и напишем.
Проблема оказалось в том, что для ~88000 часто используемых паролей это работает ОЧЕНЬ медленно. На моем компьютере это отрабатывало около 18 секунд. Пользователь не захочет ждать такое время. Значит нам нужен другой алгоритм.
Второй вариант решения: двоичный (бинарный) поиск или дихотомия
Дальше, я начал думать, как же можно было бы улучшить алгоритм. И вспомнил про двоичный поиск. Начнем с определения из вики.
Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) - классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Важно, что все слова наших паролей упорядочены по алфавиту. Схематично алгоритм выглядит так:
Схема двоичного поиска
Предположим наше слово начинается на букву F.
1. В самом начале левой точкой мы берем букву A, правой букву Z. Центральная точка у нас M.
2. M нужная нам точка? Если бы это была искомая буква, то мы ее нашли и должны закончить, но нет, это не наша точка, продолжаем алгоритм.
3. В каком отрезке может находится нужная нам точка F в AM или MZ?
4. Наша искомая точка находится в AM, тогда в качестве левой точки выбираем А, в качестве правой, выбираем M и продолжаем, переходя на шаг 1.
Вариантов окончания работы алгоритма всего два: либо мы наткнемся на эту точку на очередном шаге и нужный элемент найден, либо у нас не останется больше точек и это будет означать, что мы ничего не нашли и элемент не найден.

[@user-rb3pi2ik1p]

Таким же способом по индексам поиск работает

[@user-ix7yc3ev8w]

Очевидно, автор не застал времена СССР, когда каждый школьник знал "правило золотого сечения", т.е. если делить отрезок не пополам, а в пропорции, то скорость поиска возрастает в корень из двух раз. Враги называют подобный метод "Фибоначчи". Каждый советский учебник по прикладной математики начинался с этой главы. Увы, похоже сейчас книжки уже не читают...

[@Softonit]

Спасибо за ваш комментарий, который хорошо показывает, что «нет ничего нового под солнцем» и то, что "всё новое", это давно забытое старое! Рады, что эта тема может быть близка многим :)

[@ko6ra308]

Очередной нытик поскучал по прошлому. Шапочку из фольги надеть не забудь, когда враги 5g будут повсеместно проводить

[@Gesperid]

Причем здесь этот метод, если речь идёт про бинарный поиск? Аналог в прикладной математике - метод деления отрезка пополам (бисекции).

[@user-ix7yc3ev8w]

@@Gesperid а зачем в 21м веке делать "бинарный" поиск, когда можно тупо поделить в пропорции и на ровном месте поднять ускорение сходимости в корень из двух раз? Почему системы проектируют идиоты и закладывают уменьшение скорости поиска тупо потому что не могут отрезок делить не пополам, а в пропорции?