CodeUtility
Кодить проще - жить легче!
Алгоритмы C/C++

Линейный поиск в C и C++

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

Введение

Линейный поиск проверяет элементы по одному с начала массива, пока не найдёт искомое значение или не дойдёт до конца. Это самый простой алгоритм поиска, и он работает даже с неотсортированными данными.

Главное

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

Визуализация: Линейный поиск в C и C++

O(n)

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

Примеры кода на C и C++

C
Запустить →
main.c
#include <stdio.h>

int find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}
Результат выполнения
index=3
C++
Запустить →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Результат выполнения
index=3

Сравнение C и C++

У обеих версий сложность в худшем случае O(n). Функция find на C возвращает индекс типа int со знаком, поэтому может вернуть -1, если значение не найдено. Версия на C++ использует std::find, который возвращает итератор: если он равен values.end(), значения в массиве нет.

C

Циклы, указатели, длины и временные буферы пишутся явно.

C++

Итераторы и стандартные алгоритмы отделяют обработку от способа хранения данных.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

  • Пройдите каждое сравнение на бумаге.
  • Проверьте на повторах и на очень больших и очень маленьких значениях.
  • Измерьте время работы своего кода и сравните его со стандартной библиотекой.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи