Линейный поиск и условие остановки
Линейный поиск проверяет элементы один за другим и не требует сортировки.
В этом занятии
- Самостоятельно решить задачу по теме «Линейный поиск и условие остановки» и объяснить проверку результата.
- Миссия «Радар»: расположи искомую карточку в начале, в конце и убери её. Сравни число проверок без измерения скорости кликов.
Пригодится: informatics11-list-processing
Разберёмся перед практикой+
Линейный поиск и условие остановки
Линейный поиск проверяет элементы один за другим и не требует сортировки. Если нужен первый найденный элемент, поиск прекращается после совпадения. Если нужны все совпадения, просмотр продолжается до конца.
Число сравнений зависит от расположения искомого значения. В худшем случае первого совпадения нет или оно в конце: просматривается весь массив. Важно отдельно обозначать «не найдено», чтобы не спутать это с допустимым индексом 0.
Ищем 7 в [4,7,2,7]. Для первого вхождения достаточно двух сравнений и ответ — индекс 1; для всех вхождений нужно проверить все четыре элемента.
- Определи, нужно первое вхождение или все.
- Просматривай по порядку и явно обрабатывай отсутствие результата.
Открываем цифровую мастерскую…
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Миссия «Радар»: расположи искомую карточку в начале, в конце и убери её. Сравни число проверок без измерения скорости кликов.
- Сначала предположите результат, затем проверьте и объясните, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.