«Есть ли в списке 27 и где оно?» — самый старый вопрос, который программа задаёт о наборе данных. Ответа два: просмотреть всё — или, когда данные отсортированы, не просматривать почти ничего. Этот урок — об обоих способах.
Линейный поиск: просмотреть всё
Когда у данных нет никакого порядка, обойти это нельзя: чтобы найти x, вы
просматриваете элементы по одному, слева направо, и останавливаетесь на первом
совпадении. Это линейный поиск, и вы пишете его с недели 4 — просто не знали,
как он называется:
Тот же цикл с небольшими изменениями отвечает и на другие классические вопросы:
| Вопрос | Изменение |
|---|---|
| последнее вхождение | убрать break, чтобы последнее совпадение перезаписало pos, — или идти справа |
сколько раз встречается x | заменить pos = i; break; на count++ |
| первый элемент с нужным свойством | заменить a[i] == x на свойство: a[i] > k, a[i] == a[i + 1] |
первое совпадение внутри a[l..r] | пустить i от l до r |
Мост испытывают n машин по очереди. Каждая создаёт нагрузку; мост повреждает первая машина, нагрузка которой строго больше k. Выведите номер этой машины или -1, если такой нет.
Это тот же цикл с проверкой a[i] > k и печатью i + 1. Линейный поиск
занимает до n шагов, и для одного вопроса это нормально: 5·10⁶ элементов
просматриваются заметно быстрее, чем за секунду. Беда начинается, когда вопросов
: 10⁵ запросов к 10⁵ элементам — это 10¹⁰ шагов.