Линейный поиск на C для начинающих: как найти элемент в массиве шаг за шагом

Что делает линейный поиск​

Линейный (последовательный) поиск — простейший алгоритм нахождения элемента в массиве. Он перебирает элементы один за другим, сравнивая каждый с искомым значением, пока не найдёт совпадение или не дойдёт до конца. Никакой предварительной сортировки не требуется, дополнительных структур данных тоже.

Алгоритм выполняет не более n сравнений, где n — длина массива. В худшем случае (элемент отсутствует или стоит последним) просматриваются все n элементов. В лучшем — достаточно одного сравнения, если искомое значение стоит в начале.

Базовая реализация​

#include <stdio.h>

/*
 * Возвращает индекс первого вхождения target в массив arr
 * длины n. Если элемент не найден, возвращает -1.
 */
int linear_search(const int *arr, int n, int target)
{
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main(void)
{
    int data[] = {4, 2, 7, 1, 9, 3};
    int n = (int)(sizeof(data) / sizeof(data[0]));

    int result = linear_search(data, n, 7);

    if (result != -1) {
        printf("Элемент найден на позиции %d\n", result);
    } else {
        printf("Элемент не найден\n");
    }

    return 0;
}

Вывод программы:

Элемент найден на позиции 2

Разбор по шагам​

1. Функция получает указатель на начало массива, его длину и искомое значение.
   
2. Цикл for проходит от индекса 0 до n - 1.
   
3. На каждой итерации arr[i] сравнивается с target.
   
4. При совпадении функция немедленно возвращает текущий индекс.
   
5. Если цикл завершился без совпадения, возвращается -1 — сигнал «не найдено».
   

Возврат -1 безопасен, потому что в C индексы массива всегда неотрицательны. Это общепринятое соглашение для функций поиска.

Поиск всех вхождений​

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

#include <stdio.h>

/*
 * Записывает индексы всех вхождений target в out_indices.
 * Возвращает количество найденных вхождений.
 * max_results — вместимость буфера out_indices.
 */
int linear_search_all(const int *arr, int n, int target,
                      int *out_indices, int max_results)
{
    int count = 0;
    for (int i = 0; i < n && count < max_results; i++) {
        if (arr[i] == target) {
            out_indices[count] = i;
            count++;
        }
    }
    return count;
}

int main(void)
{
    int data[] = {3, 5, 3, 8, 3, 1};
    int n = (int)(sizeof(data) / sizeof(data[0]));
    int indices[16];

    int found = linear_search_all(data, n, 3, indices, 16);

    printf("Найдено %d вхождений: ", found);
    for (int i = 0; i < found; i++) {
        printf("%d ", indices[i]);
    }
    printf("\n");

    return 0;
}

Вывод:

Найдено 3 вхождений: 0 2 4

Здесь важно не переполнить буфер out_indices. Параметр max_results ограничивает запись и защищает от выхода за границы выделенной памяти.

Оптимизация с sentinel​

Классический цикл выполняет два сравнения на итерацию: arr[i] == target и i < n. Если добавить в конец массива копию искомого значения (sentinel), проверку границы можно убрать из тела цикла — поиск гарантированно остановится на sentinel или раньше.

#include <stdio.h>

/*
 * Требует, чтобы arr имел хотя бы n + 1 выделенных элементов.
 * arr[n] используется как sentinel.
 */
int sentinel_search(int *arr, int n, int target)
{
    int last = arr[n];   /* сохраняем оригинальное значение */
    arr[n] = target;     /* ставим sentinel */

    int i = 0;
    while (arr[i] != target) {
        i++;
    }

    arr[n] = last;       /* восстанавливаем */

    if (i < n) {
        return i;        /* найдено внутри массива */
    }
    return -1;           /* сработал sentinel */
}

int main(void)
{
    int data[8] = {10, 20, 30, 40, 50, 60, 70, 0};
    int n = 7;  /* логическая длина, data[7] — резерв под sentinel */

    int pos = sentinel_search(data, n, 40);
    printf("Позиция: %d\n", pos);  /* Позиция: 3 */

    return 0;
}

Ограничения sentinel-подхода​

• Массив должен быть изменяемым (int *, не const int *).
  
• За массивом нужен хотя бы один свободный слот.
  
• Если массив выделен ровно под n элементов (например, через malloc(n * sizeof(int))), запись в arr[n] — неопределённое поведение. Нужно выделять n + 1.
  

Для учебных задач и небольших массивов выигрыш минимален, но на больших данных экономия одного сравнения на итерацию заметна.

Ранняя остановка в отсортированном массиве​

Если массив отсортирован по возрастанию, можно прекратить поиск, как только текущий элемент превысил искомое значение. Это не меняет худшую сложность (по-прежнему O(n)), но сокращает среднее число сравнений, когда элемент отсутствует.

#include <stdio.h>

/*
 * arr должен быть отсортирован по возрастанию.
 */
int linear_search_sorted(const int *arr, int n, int target)
{
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
        if (arr[i] > target) {
            return -1;  /* дальше искать бессмысленно */
        }
    }
    return -1;
}

Если массив уже отсортирован и поиск выполняется многократно, бинарный поиск (O(log n)) будет значительно быстрее. Линейный поиск по отсортированному массиву оправдан только при однократном запросе или очень малом n.

Сложность​

Случай	Число сравнений	Асимптотика
Лучший (элемент первый)	1	O(1)
Средний (элемент встречается один раз, позиция равномерна)	(n + 1) / 2	O(n)
Худший (элемент последний или отсутствует)	n	O(n)

Пространственная сложность — O(1): алгоритм использует только несколько целочисленных переменных независимо от размера входных данных.

Типичные ошибки начинающих​

Выход за границы массива​

/* ОШИБКА: условие i <= n читает arr[n], которого не существует */
for (int i = 0; i <= n; i++) {
    if (arr[i] == target) return i;
}

Правильно: i < n. Индексация в C начинается с нуля, последний допустимый индекс — n - 1.

Неинициализированная длина​

int arr[100];
/* заполнено только 5 элементов */
int n;  /* не инициализировано! */
linear_search(arr, n, 42);  /* неопределённое поведение */

Всегда передавайте реальное количество заполненных элементов, а не размер буфера.

Сравнение чисел с плавающей точкой​

/* Ненадёжно для double/float */
if (arr[i] == target)

Для float и double прямое сравнение == может не сработать из-за ошибок округления. Используйте сравнение с допуском:

#include <math.h>

#define EPSILON 1e-9

if (fabs(arr[i] - target) < EPSILON) {
    return i;
}

Переполнение индекса​

Если n близок к INT_MAX, выражение i + 1 внутри цикла может переполниться. На практике массивы такого размера в стеке не размещают, но при работе с динамической памятью и типом size_t стоит использовать беззнаковый счётчик:

for (size_t i = 0; i < n; i++) { ... }

Когда линейный поиск уместен​

• Массив содержит мало элементов (условно до ~100).
  
• Поиск выполняется однократно, сортировка ради одного запроса нецелесообразна.
  
• Данные неупорядочены и их порядок нельзя менять.
  
• Массив часто изменяется, и поддержание отсортированного состояния дороже, чем последовательный перебор.
  

Когда поиск выполняется многократно по одному и тому же массиву, имеет смысл отсортировать данные и перейти к бинарному поиску или построить хеш-таблицу.

Проверка результата​

После вызова функции поиска всегда проверяйте возвращаемое значение:

int idx = linear_search(data, n, target);
if (idx >= 0 && idx < n) {
    /* безопасное использование data[idx] */
} else {
    /* элемент не найден — обработать ситуацию */
}

Условие idx >= 0 защищает от использования -1 как индекса. Условие idx < n избыточно для корректной реализации, но полезно как защитная проверка при отладке.

Итоговый чек-лист​

• Функция принимает const int *arr, int n, int target и возвращает индекс или -1.
  
• Цикл использует i < n, не i <= n.
  
• Для float/double применяется сравнение с epsilon.
  
• При поиске всех вхождений буфер результатов ограничен по размеру.
  
• Sentinel-вариант требует дополнительного слота за пределами логической длины массива.
  
• Для многократного поиска по одному массиву рассмотрите сортировку + бинарный поиск.
  

Источники​

• Linear search - Wikipedia
  
• Main Page - Algorithms for Competitive Programming
  

 

[zer0coder]

Расскажи про сложность алгоритмов О.

 

[Qwen]

Нотация «О» — что это на самом деле​

«О» (Big O) — это способ описать, как быстро растёт время выполнения (или память) алгоритма при увеличении размера входных данных. Формально это асимптотическая верхняя граница: f(n) = O(g(n)) означает, что при достаточно больших n время выполнения не превышает C * g(n) для некоторой константы C.

Ключевая идея: константы и младшие члены отбрасываются. Нас интересует только порядок роста.

Основные классы сложности​

O(1) — константная. Время не зависит от размера данных. Пример: доступ к элементу массива по индексу arr[i], вставка в начало хеш-таблицы.

O(log n) — логарифмическая. Рост очень медленный. Пример: бинарный поиск в отсортированном массиве, поиск в сбалансированном дереве.

O(n) — линейная. Время растёт пропорционально размеру данных. Пример: линейный поиск, проход по массиву.

O(n log n) — линейно-логарифмическая. Пример: быстрая сортировка, сортировка слиянием.

O(n²) — квадратичная. Пример: пузырьковая сортировка, вложенные циклы по одному массиву.

O(2ⁿ) — экспоненциальная. Пример: рекурсивный перебор всех подмножеств.

O(n!) — факториальная. Пример: перебор всех перестановок.

Как читать запись​

O(n) — это не «ровно n операций». Это «порядок роста — линейный». Реальное число операций может быть 3n + 5 или 0.5n + 100, но при больших n всё это — O(n).

Правила упрощения:

• Отбрасываем константы: O(2n) → O(n), O(100) → O(1).
• Оставляем только доминирующий член: O(n² + n) → O(n²).
• Логарифм без основания: O(log₂ n) и O(log₁₀ n) — одно и то же, потому что отличаются на константу.

Анализ на практике​

Один цикл:

for (int i = 0; i < n; i++) {
    // O(1) операций
}

Сложность — O(n). Каждая итерация — константа, итераций — n.

Вложенные циклы:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1) операций
    }
}

Сложность — O(n²). Внешний цикл выполняется n раз, внутренний — n раз для каждой итерации внешнего.

Цикл с уменьшением шага:

for (int i = 0; i < n; i *= 2) {
    // O(1) операций
}

Сложность — O(log n). Количество итераций — примерно log₂ n.

Рекурсия:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Сложность — O(2ⁿ). Каждый вызов порождает два новых. Для n = 40 это уже миллиарды операций.

Лучший, средний, худший случай​

Для одного алгоритма можно указать три оценки:

• Лучший — минимальное время при удачных данных.
• Средний — математическое ожидание при случайных данных.
• Худший — максимальное время при неблагоприятных данных.

Для линейного поиска:

• Лучший: O(1) — элемент первый.
• Средний: O(n) — элемент где-то в середине.
• Худший: O(n) — элемент последний или отсутствует.

Обычно под «сложностью алгоритма» подразумевают худший случай, если не оговорено иное.

Сложность по памяти​

Помимо времени, оценивают и память. Для линейного поиска — O(1): используются только несколько переменных, независимо от размера массива. Для сортировки слиянием — O(n): нужен дополнительный буфер размером с массив.

Практические советы​

• Big O — не единственный критерий. Для n = 10 алгоритм с O(n²) может быть быстрее, чем с O(n log n), из-за меньших констант.
• Измеряйте реальную производительность. Big O говорит о масштабировании, но не о фактическом времени. Профилирование (perf, gprof, valgrind --tool=callgrind) покажет реальную картину.
• Смотрите на доминирующую операцию. Если в цикле вызывается функция с O(n), общая сложность — O(n²).
• Амортизационная сложность. Некоторые операции «дорогие» редко, но в среднем дёшевы. Пример: вставка в динамический массив — O(n) в худшем случае, но O(1) амортизированно.

Пример анализа​

int sum_and_count(int *arr, int n, int target) {
    int sum = 0;
    int count = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];              // O(1)
        if (arr[i] == target) {
            count++;                // O(1)
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                count++;            // O(1)
            }
        }
    }

    return sum + count;
}

Первый цикл — O(n). Второй — вложенный, количество итераций n(n-1)/2, то есть O(n²). Общая сложность — O(n²), потому что доминирует второй цикл.

Как проверять на практике​

Для небольших n можно замерить время и убедиться, что рост соответствует ожидаемому:

# для O(n): увеличение n в 2 раза увеличивает время примерно в 2 раза
# для O(n²): увеличение n в 2 раза увеличивает время примерно в 4 раза
# для O(log n): увеличение n в 2 раза добавляет константу к времени

Используйте time в Linux или clock_gettime в коде для точных замеров.