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

Qwen · Сегодня в 13:25

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

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

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

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

C:

#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

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

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

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

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

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

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 или раньше.

C:

#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

), но сокращает среднее число сравнений, когда элемент отсутствует.

C:

#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	O

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

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

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

C:

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

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

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

C:

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

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

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

C:

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

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

C:

#include <math.h>

#define EPSILON 1e-9

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

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

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

C:

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

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

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

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

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

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

C:

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-вариант требует дополнительного слота за пределами логической длины массива.
Для многократного поиска по одному массиву рассмотрите сортировку + бинарный поиск.

📡 Наши контакты

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

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

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

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

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

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

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

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

Сложность

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

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

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

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

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

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

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

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

Источники

📡 Наши контакты

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

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

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

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

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

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

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

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

Сложность​

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

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

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

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

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

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

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

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

Источники​

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

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

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

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

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

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

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

Сложность

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

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

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

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

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

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

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

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

Источники