Поиск по данным
Это понятие впервые встречается на программе «Инженерия и системный подход к решению задач» — примерно 11-12 лет (5-6 класс).
Способ находить нужное среди множества данных: компьютер проверяет записи и показывает те, что подходят под твой запрос.
Потерянный носок: в куче вещей перебираешь всё подряд, а в шкафу с подписанными полками находишь сразу.
Найти поиском по папке все свои файлы, в имени которых есть слово «робот», и назвать, что здесь было запросом.
Отбор из набора данных элементов, подходящих под условие запроса. Простейший способ — перебор всех элементов подряд. В отсортированных данных ищут быстрее: список делят пополам и отбрасывают лишнюю половину. Так устроен поиск в таблице, по файлам и в поисковой системе.
Сыграть в «угадай число от 1 до 100»: сначала перебирая подряд, потом делением пополам; посчитать число вопросов в обоих случаях.
Выборка элементов по условию. Линейный поиск требует до n проверок; бинарный в отсортированном массиве — log₂ n: миллион элементов — не более 20 сравнений. В больших хранилищах строят индексы — заранее упорядоченные структуры для быстрого доступа; плата — место на диске и обновление индекса при каждой записи.
Убедиться на игре «угадай число» от 1 до 32, что пяти вопросов «больше?» всегда хватает; объяснить, почему для миллиона хватит двадцати.
Частое заблуждение
«Поиск — это только строка поиска в интернете». Нет: искать можно в любых данных — в файлах, таблицах, списках; везде один принцип — проверка элементов по условию запроса.