Журнал кодов заказов

У нас есть журнал кодов заказов: [42, 17, 42, 58, 17]. Коды записаны в том порядке, в каком заказы поступали. Нам нужно найти первое вхождение кода 42. Спрашивается: как это сделать?

Мы уже умеем проходить по массиву циклом. Значит, можно просто идти слева направо и смотреть на каждый элемент: совпадает ли он с 42. Как только нашли — остановились и запомнили позицию. Если дошли до конца и не нашли — значит, такого кода нет.

Это и есть линейный поиск: мы последовательно просматриваем элементы, пока не найдём нужный или пока не закончится массив. Название "линейный" отражает, что время работы растёт линейно с длиной массива.

Индекс и значение: не перепутать

Здесь важно сразу различить две вещи: значение элемента и его индекс. В нашем журнале значение 42 встречается дважды: на позициях 0 и 2. Если мы ищем код 42, ответом будет индекс 0 — позиция первого вхождения. Значение 42 — это то, что мы ищем, а индекс 0 — это то, что мы возвращаем.

Почему это важно? Потому что можно случайно вернуть значение вместо индекса. Или перепутать, что именно означает 0. В программировании индекс 0 — это валидная позиция, первый элемент массива. А если элемента нет, нам нужно как-то об этом сообщить. Обычно для этого используют -1, потому что -1 не может быть валидным индексом. Так мы различаем "нашли на позиции 0" и "не нашли вообще".

"Любой", "первый" и "все"

Прежде чем писать код, стоит уточнить, что именно мы ищем. Задача "найти 42" может означать три разные вещи. Первая: найти любой элемент со значением 42 — неважно, какой именно. Вторая: найти первый такой элемент. Третья: найти все такие элементы.

Для нашего журнала [42, 17, 42, 58, 17] ответы будут разными. "Любой" может вернуть позицию 0 или 2 — как повезёт. "Первый" всегда вернёт 0. "Все" вернёт 0 и 2.

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

Инвариант: слева от i искомого нет

Когда мы идём по массиву слева направо, полезно сформулировать, что мы знаем на каждом шаге. Пусть i — текущий индекс, который мы рассматриваем. Тогда все элементы с индексами от 0 до i − 1 уже проверены, и среди них искомого нет. Это и есть инвариант: слева от i искомого нет.

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

В начале, когда i = 0, слева от i нет элементов, поэтому инвариант выполняется автоматически. На каждом шаге мы смотрим на a[i]. Если это не искомое значение, мы переходим к i + 1, и инвариант сохраняется: теперь слева от нового i находятся все элементы, которые были слева от старого i, плюс сам старый a[i], который мы только что проверили и не нашли. Если же a[i] совпало с искомым, мы возвращаем i — и это первое вхождение, потому что слева искомого не было.

Ранний возврат

Отсюда следует важная деталь: как только мы нашли совпадение, нужно сразу вернуть результат и остановиться. Не продолжать цикл, не искать дальше. Потому что первый ответ уже найден, а все последующие вхождения нас не интересуют.

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

Программа FindFirst

Соберём это в программу. Метод FindFirst принимает массив и искомое значение, возвращает индекс первого вхождения или -1, если такого значения нет.

using System;

int[] orders = { 42, 17, 42, 58, 17 };

Console.WriteLine(FindFirst(orders, 42));
Console.WriteLine(FindFirst(orders, 17));
Console.WriteLine(FindFirst(orders, 99));
Console.WriteLine(FindFirst(Array.Empty<int>(), 42));

int FindFirst(int[] a, int target)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] == target) return i;
    }
    return -1;
}

Вывод:

0
1
-1
-1

Разберём тесты. FindFirst(orders, 42) возвращает 0: первое вхождение 42 — на позиции 0. FindFirst(orders, 17) возвращает 1: первое вхождение 17 — на позиции 1. FindFirst(orders, 99) возвращает −1: значения 99 в массиве нет. FindFirst(Array.Empty

Обратите внимание на пустой массив. Цикл не выполняется ни разу, мы сразу доходим до return -1. Это корректно: в пустом массиве нет ни одного элемента, значит, искомого значения точно нет.

Особые случаи

Разберём несколько ситуаций, которые полезно проверять в уме.

Пустой массив: ответ −1, как мы видели. Единственный элемент: если он совпадает с искомым, ответ 0; если нет — −1. Дубликаты: если значение встречается несколько раз, мы возвращаем первое вхождение, потому что останавливаемся на нём. Совпадение последним элементом: придётся пройти весь массив до конца, и ответ будет n − 1. Здесь ранний возврат не поможет: мы дойдём до последнего элемента и только там найдём совпадение.

Стоимость

Оценим работу FindFirst. В худшем случае, когда искомого значения нет или оно стоит последним, мы просматриваем все n элементов. Значит, время — O(n). В лучшем случае, когда совпадение на первом элементе, мы делаем одно сравнение и возвращаемся: O(1). Но это именно лучший случай, а не гарантия. Для оценки сверху нас интересует худший случай O(n).

Дополнительная память — O(1): мы используем только счётчик i и само искомое значение. Массив мы не копируем и не меняем.

Все совпадения: другая задача

Теперь представим, что нам нужно не первое вхождение, а все позиции, где встречается код 42. Это другая задача, и решается она иначе.

Мы по-прежнему идём по массиву слева направо. Теперь слева от i могут быть искомые значения, но мы уже записали их позиции в результат. Инвариант можно переформулировать: все позиции искомого значения, которые встречаются слева от i, уже добавлены в результат.

Когда мы находим совпадение, мы не возвращаемся сразу, а добавляем позицию в список и продолжаем движение. Только когда массив закончился, мы возвращаем весь список.

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

Программа FindAll

Соберём вторую программу. Метод FindAll принимает массив и искомое значение, возвращает список индексов всех вхождений. Если совпадений нет, возвращается пустой список.

using System;
using System.Collections.Generic;

int[] orders = { 42, 17, 42, 58, 17 };

var positions = FindAll(orders, 42);
if (positions.Count == 0) Console.WriteLine("нет совпадений");
else Console.WriteLine(string.Join(" ", positions));

var none = FindAll(orders, 99);
if (none.Count == 0) Console.WriteLine("нет совпадений");

var empty = FindAll(Array.Empty<int>(), 42);
if (empty.Count == 0) Console.WriteLine("нет совпадений");

List<int> FindAll(int[] a, int target)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    var result = new List<int>();
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] == target) result.Add(i);
    }
    return result;
}

Вывод:

0 2
нет совпадений
нет совпадений

Для 42 мы получаем позиции 0 и 2. Для 99 — пустой список, и мы явно печатаем "нет совпадений". Для пустого массива — тоже пустой список.

Память и стоимость FindAll

Время работы FindAll — O(n) в любом случае, потому что мы всегда просматриваем весь массив. Ранний возврат здесь невозможен: даже если все совпадения уже найдены, мы не знаем, есть ли ещё, пока не дойдём до конца.

Память: результат занимает O(k), где k — число совпадений. В худшем случае, когда все элементы равны искомому, k = n, и память результата O(n). Вспомогательная память, помимо результата, — O(1): счётчик i и сама ссылка на список. Добавления в List амортизированно O(1) каждое, поэтому общее время с учётом добавлений остаётся O(n).

Входной массив не меняется. Мы только читаем его элементы и записываем индексы в отдельный список.

Что мы получили

Линейный поиск — это базовый инструмент, который стоит освоить до более сложных алгоритмов. Он не требует никакой предварительной подготовки данных: ни сортировки, ни структуры, ни индексов. Просто проход по массиву слева направо.

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

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