Задачи / Поиск / Линейный поиск элемента в массиве

Линейный поиск элемента в массиве: блок-схема и алгоритм

Просматриваем элементы по порядку, пока не найдём искомый x или не дойдём до конца массива. Если дошли до конца — элемента нет.

Блок-схема: Линейный поиск элемента в массиве

Алгоритм по шагам

Ввести n, массив a и искомое значение x.
Присвоить i = 1.
Пока i ≤ n и a[i] ≠ x — увеличивать i.
Если i ≤ n — элемент найден на позиции i, иначе — не найден.

Открыть блок-схему в редакторе

Пример работы

Вход	a = [8, 3, 6, 3], x = 6
Шаг 1	i = 1: a[1] = 8 ≠ 6
Шаг 2	i = 2: a[2] = 3 ≠ 6
Шаг 3	i = 3: a[3] = 6 — цикл остановлен
Результат	найден, номер 3

Решение на Python

n = int(input())
a = list(map(int, input().split()))
x = int(input())
i = 0
while i < n and a[i] != x:
    i += 1
if i < n:
    print("найден, номер", i + 1)
else:
    print("не найден")

Решение на Pascal

var a: array[1..100] of integer;
    n, i, x: integer;
begin
  readln(n);
  for i := 1 to n do read(a[i]);
  readln(x);
  i := 1;
  while (i <= n) and (a[i] <> x) do
    i := i + 1;
  if i <= n then writeln('найден, номер ', i)
  else writeln('не найден');
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: Линейный поиск
начало
ввод n, массив a[1..n], x
i = 1
пока i ≤ n и a[i] ≠ x
    i = i + 1
если i ≤ n
    вывод «найден, номер», i
иначе
    вывод «не найден»
конец

Сложность

O(n) в худшем случае. Работает на любом массиве, сортировка не нужна.

Частые ошибки

Поменять условия местами (сначала a[i] ≠ x): при i = n + 1 обращение за границу массива.
Проверять результат по a[i] = x после цикла — при i > n это тоже выход за границу.
Использовать цикл «для» без выхода — тогда найдётся последнее вхождение, а не первое.