5.2. Поиск одного элемента, удовлетворяющего условию поиска
Содержание
Для поиска одного подходящего элемента массив последовательно просматривают и сравнивают a[i] с заданным значением или условием. Наличие совпадения можно запомнить логической переменной, а место - индексом. Если нужен первый подходящий элемент, цикл завершают сразу после находки; для упрощения условия остановки можно использовать дополнительный элемент-барьер.
Что нужно понять
- Логическую переменную p инициализируют значением false, а при обнаружении совпадения изменяют на true.
- Если нужен индекс, вводят переменную k и первоначально задают ей ноль.
- Полный перебор с присваиванием k := i для каждого совпадения оставляет индекс последнего подходящего элемента.
- При поиске первого совпадения цикл while может остановиться сразу после его обнаружения.
- Если совпадения не было, после перебора проверяют специальное значение индекса.
- Метод барьера добавляет в конец дополнительный элемент, равный искомому значению.
- При использовании барьера следует отличать совпадение внутри исходного массива от срабатывания дополнительного элемента.
Видео
Скачать к теме
Главное по теме
В поиске одного элемента важно заранее определить, требуется ли только факт совпадения или его позиция, и когда прекращать просмотр.
Ключевые понятия
Как это работает
Что нужно запомнить
- k = 0 после полного перебора означает, что совпадения не были найдены, если индексы исходного массива начинаются с единицы.
- Барьер принадлежит дополнительной позиции и не считается найденным исходным элементом.
Проверь себя
Как начально задают логическую переменную p при поиске совпадения?
Какой индекс останется в k после полного прохода и присваивания k := i на каждом совпадении?
Как ускоряют поиск первого совпадения при ранней находке?
Какую роль выполняет барьер при поиске?
Как отличить отсутствие элемента при поиске с барьером?