Задания № 6, 10 · ЕГЭ

Поиск элемента в массиве

Линейный просмотр массива: как проверить наличие элемента и найти первое совпадение

6 мин чтенияСложность: Обновлено 29 сентября 2026

Поиск элемента в массиве — это последовательная проверка его элементов до тех пор, пока не найдено нужное значение или не просмотрен весь массив. Такой алгоритм позволяет определить, есть ли элемент в массиве, и найти позицию его первого совпадения.

Идея линейного поиска

Линейный поиск выполняется слева направо: сначала сравнивается первый элемент массива с искомым значением, затем второй и так далее. Если найдено равенство, поиск можно завершить. Если просмотрен весь массив и совпадения нет, делается вывод, что элемент отсутствует.

Линейный поиск

Линейный поиск — алгоритм последовательной проверки элементов массива на равенство искомому значению. Его также называют последовательным поиском.

Перед написанием поиска важно определить, что именно требуется получить: логический ответ «есть ли элемент», количество совпадений или индекс первого совпадения. Во всех случаях используется перебор массива, но условие внутри цикла и результат могут различаться.

Проверка наличия: достаточно переменной-флага или немедленного вывода ответа.
Позиция первого совпадения: при первом равенстве нужно сохранить индекс и прекратить поиск.
Количество совпадений: нужно просмотреть весь массив, увеличивая счётчик при каждом равенстве.

Правило остановки

Если требуется найти первое совпадение, поиск прекращают сразу после обнаружения равенства. Все элементы правее найденного уже не могут изменить позицию первого совпадения.

Индексы и границы поиска

Пусть массив $a$ содержит $n$ элементов. В школьных алгоритмах его элементы часто нумеруются от $0$ до $n-1$ в Python и C++, а в Паскале обычно от $1$ до $n. Нельзя смешивать эти соглашения: ошибка в границах цикла приводит к пропуску элемента или обращению за пределы массива.

\[0 \le i < n \quad \text{для индексации с нуля}\]

\[1 \le i \le n \quad \text{для индексации с единицы}\]

Если в условии спрашивается «номер элемента», заранее проверьте, имеется ли в виду индекс или позиция. В Python индекс первого элемента равен $0$, но его человеческая позиция — $1$. Например, для массива $[7, 4, 9]$ число $4$ имеет индекс $1$ и позицию $2$.

Частая ошибка: перепутать индекс и позицию

При индексации с нуля найденный индекс не всегда совпадает с требуемым номером элемента. Если в ответе нужна позиция, а найден индекс $i$, выведите $i+1$.

Для проверки наличия удобно завести переменную found. В начале она равна False. При совпадении она становится True. Если нужна позиция, можно использовать значение -1 как признак того, что элемент пока не найден.

\[\text{position} = \begin{cases} i, & \text{если } a_i=x;\\ -1, & \text{если совпадений нет.} \end{cases}\]

Python

1a = [8, 3, 6, 3, 10]
2x = 3
3
4position = -1
5for i in range(len(a)):
6    if a[i] == x:
7        position = i
8        break
9
10print(position)

В этом фрагменте будет напечатано 1: первое число $3$ стоит под индексом $1$. Второе такое число не рассматривается, потому что команда break завершает цикл после первого совпадения.

Проверка наличия и первое совпадение

Проверка наличия отвечает только на вопрос, встречается ли значение $x$ в массиве. В логической форме условие выглядит так: существует ли такой индекс $i$, что $a_i=x$. На практике достаточно просмотреть массив и изменить флаг при найденном совпадении.

\[\operatorname{exists}(x)=\begin{cases} \text{True},&\exists i:\ a_i=x;\\\text{False},&\text{иначе.}\end{cases}\]

При поиске первого совпадения важно не перезаписывать найденную позицию. Если цикл продолжается после первого равенства, переменная в конце будет содержать позицию последнего совпадения. Поэтому применяют break или условие вида if position == -1.

Микропроверка

Массив имеет вид $[5, 2, 5, 7]$. Какой индекс первого совпадения с числом $5$ при нумерации с нуля?

Разобранный пример

Дан массив из $n$ целых чисел и число $x$. Требуется вывести индекс первого элемента, равного $x$, или $-1$, если такого элемента нет. Рассмотрим массив $[12, 7, 4, 7, 9]$ и значение $x=7$.

№

Пример: поиск первого совпадения

Массив индексируется с нуля. Начальное значение позиции — $-1$, то есть совпадение ещё не найдено.

До начала просмотра считаем, что нужного элемента нет.

p=-1

Проверяем индекс $0$: $a_0=12$, равенство $12=7$ неверно.

p=-1

Проверяем индекс $1$: $a_1=7$, равенство верно.

p=1

После первого совпадения поиск прекращаем; индекс $3$ уже не рассматриваем.

$\displaystyle \boxed{p=1}$

Python

1a = [12, 7, 4, 7, 9]
2x = 7
3
4p = -1
5for i in range(len(a)):
6    if a[i] == x:
7        p = i
8        break
9
10print(p)

Ответ программы — 1. Если бы требовалась позиция элемента, отсчёт в условии шёл с единицы, и ответом было бы $p+1=2$.

Частые ошибки в алгоритме

1. Проверять только часть массива из-за неверной границы цикла. 2. Использовать break при подсчёте количества совпадений: тогда будут найдены не все элементы. 3. Не инициализировать позицию значением $-1$. 4. После нахождения элемента продолжать цикл и случайно получать последнее, а не первое совпадение. 5. Сравнивать индекс с искомым значением вместо элемента массива: нужно писать a[i] == x.

Сложность и варианты реализации

В худшем случае линейный поиск проверяет все $n$ элементов: искомого значения нет или оно стоит в конце. В лучшем случае достаточно одной проверки — если элемент находится в начале. Дополнительная память обычно не зависит от размера массива.

\[T(n)=O(n),\qquad S(n)=O(1)\]

Если массив не отсортирован, линейный поиск является универсальным способом проверки. Для отсортированных данных могут существовать более быстрые методы, но в обычной задаче экзамена сначала нужно внимательно прочитать условие: часто требуется простой перебор с подходящим условием.

Поиск в строке устроен аналогично: символы рассматриваются по очереди, а искомым значением становится символ или фрагмент. При более сложной обработке полезны темы таблица частот символов и сравнение строк. Если требуется удалять повторения или анализировать несколько совпадений, пригодятся уникальные элементы и повторяющиеся фрагменты.

Как выбрать алгоритм

Сначала запишите словами, что должна означать переменная результата. Например: «p — индекс первого найденного элемента или $-1$, если его нет». После этого легко подобрать начальное значение, условие сравнения и момент остановки.

Быстрый тест по теме

Проверь себя

~ 2 мин4 вопроса

Вопрос 1 / 4

Вопрос 1 из 4 · индексы

Какой индекс имеет первый элемент массива при нумерации с нуля?

Главное за минуту

Главное

Линейный поиск последовательно сравнивает элементы массива с искомым значением.
Для проверки наличия достаточно получить логический результат, а для первого совпадения — сохранить индекс и остановить цикл.
При индексации с нуля индексы лежат от $0$ до $n-1$; индекс и человеческая позиция могут различаться.
Если совпадение не найдено, удобно использовать специальное значение $-1$.
Сложность линейного поиска — $O(n)$ по времени и $O(1)$ по дополнительной памяти.