сравнения.
Есть массив из тысячи объектов (пользователей с числовым ID), объекты не упорядочены. Какая будет сложность алгоритма поиска по этому массиву?
сравнения.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
3 сравнения.
Данную задачу можно решить с помощью алгоритма бинарного поиска. Для массива из 8 элементов, отсортированных по возрастанию, каждое сравнение сужает область поиска вдвое.
Вот как это работает:
- Первое сравнение: Сравниваем искомый элемент с элементом посередине массива (индекс 3 или 4, в зависимости от начального индексации). Если элементы совпадают, поиск завершен. Если искомый элемент меньше, продолжаем поиск в левой половине массива. Если больше, то в правой.
- Второе сравнение: В выбранной половине массива (теперь она из 4 элементов) снова сравниваем искомый элемент с элементом посередине. Если нашли, отлично. Иначе, продолжаем поиск в одной из половин этой "четвертушки" (по 2 элемента).
- Третье сравнение: В оставшейся паре элементов сравниваем искомый с одним из них. Найден ли элемент или нет, после этого сравнения мы точно знаем результат.
Математически это можно выразить логарифмом по основанию 2: log₂(8) = 3.