Алгоритмы поиска

Поиск в отсортированном массиве делением пополам. Сравнение с серединой, отбрасывание половины. Сложность O(log n). Рекурсивная и итеративная реализации. Требует предварительной сортировки.

Последовательный перебор элементов до нахождения. Сложность O(n). Не требует сортировки. Применяется для малых массивов, несортированных данных, связных списков. Простейший алгоритм поиска.

Улучшение бинарного поиска для равномерно распределённых данных. Оценка позиции элемента по формуле интерполации. Средняя сложность O(log log n), худшая O(n). Эффективен для числовых диапазонов.

Поиск диапазона с удвоением индекса (1, 2, 4, 8...), затем бинарный поиск в диапазоне. Сложность O(log n). Эффективен для неограниченных массивов, когда размер неизвестен.

Прыжки по массиву с шагом √n, затем линейный поиск в блоке. Сложность O(√n). Требует сортировки. Компромисс между линейным и бинарным. Эффективен для систем с дорогими сравнениями.

Поиск делением пополам в отсортированном массиве (идея из 1946). O(log n) сравнений. Требует random access. Основа для деревьев поиска, интерполяционного поиска.

Последовательный перебор элементов. O(n) в среднем и худшем случае. Единственный вариант для неотсортированных данных. Оптимален при однократном поиске.

Вычисляет хеш ключа, получает адрес за O(1). Требует хеш-таблицу. Коллизии решаются цепочками или открытой адресацией. Самый быстрый для точного поиска.