1. Асимптотика Бинарный поиск

Бинарный поиск (другие названия — двоичный поиск, метод половинного деления, дихотомия) — тип поискового алгоритма, который последовательно делит пополам заранее отсортированный массив данных, чтобы обнаружить нужный элемент. Принцип работы: Сортируем массив данных. Делим его пополам и находим середину. Сравниваем срединный элемент с заданным искомым элементом. Если искомое число больше среднего — продолжаем поиск в правой части массива (если он отсортирован по возрастанию): делим её пополам, повторяя пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой части массива, снова возвращаясь к пункту 3. Бинарный поиск используется в информатике, вычислительной математике и математическом программировании. Некоторые ограничения: алгоритм не работает с неотсортированными данными и не применим для графов. Также бинарный поиск неэффективен при частых изменениях данных. O(log n) — асимптотическая сложность бинарного поиска в отсортированном массиве. Это означает, что время выполнения алгоритма растёт логарифмически с увеличением размера входного массива (n). Это означает, что при увеличении размера массива в два раза время выполнения алгоритма увеличится примерно в два раза. Доказательство Бинарный поиск разделяет массив пополам на каждой итерации. Поиск начинается с середины массива. Если значение, которое нужно найти, больше среднего элемента, поиск продолжается в правой половине массива, если оно меньше — в левой. Таким образом, на каждой итерации...