В прошлом блоке мы разбирали базовые структуры данных — массивы, связные списки, стеки, очереди, множества. Вы научились хранить данные. Но хранить — это полдела. Данные нужны для того, чтобы с ними работать: сортировать, фильтровать и, конечно, искать.

Задумайтесь: почти любая программа — это, по сути, поиск. Поисковик ищет страницы по запросу. Интернет-магазин ищет товар по названию. Навигатор ищет кратчайший маршрут. Даже автозаполнение в мессенджере — это поиск подходящего слова. Вопрос не в том, нужен ли поиск, а в том, как искать эффективно.

Добро пожаловать в блок «Алгоритмы поиска». Здесь мы научимся отвечать на простой вопрос: «Есть ли нужный элемент в коллекции, и если да — где он?» Начнём с самого простого и интуитивного подхода — линейного поиска. Представьте: вы пришли в библиотеку, и вам нужна книга «Чистый код» Роберта Мартина. Библиотекарь в отпуске, каталог не работает. Что вы сделаете? Пойдёте вдоль полок и будете смотреть каждую книгу по очереди: первая — не та, вторая — не та, третья... пока не найдёте нужную или пока полки не закончатся.

Поздравляю — вы только что выполнили линейный поиск. Без всяких учебников по алгоритмам.

Звучит примитивно? Может быть. Но именно так работает поиск в большинстве программ, когда данные не отсортированы. И именно этот алгоритм вы неосознанно писали каждый раз, когда использовали цикл for для нахождения элемента в массиве.

Визуализируем. У нас массив оценок студентов, и мы ищем первую пятёрку:

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

Теперь то же самое в коде:

int[] grades = { 3, 4, 2, 5, 4, 5, 3 };
int target = 5;

int foundIndex = -1;
for (int i = 0; i < grades.Length; i++)
{
    if (grades[i] == target)
    {
        foundIndex = i;
        break; // нашли — дальше не идём
    }
}

Console.WriteLine(foundIndex); // 3

Три ключевых момента. Первый: мы идём по массиву слева направо, проверяя каждый элемент. Второй: как только нашли совпадение — выходим из цикла через break. Нет смысла проверять оставшиеся элементы, если нас интересует только первое вхождение. Третий: если элемент не найден, foundIndex останется равным -1 — это стандартное соглашение, означающее «не найдено». Почему именно -1? Потому что это значение никогда не может быть валидным индексом массива — индексы начинаются с нуля. Окей, поиск конкретного значения — это базовый случай. Но на практике задачи бывают разнообразнее. Оформим линейный поиск как метод и посмотрим на несколько вариаций.

Первая — классический поиск по значению. Возвращает индекс первого вхождения:

static int LinearSearch(int[] items, int target)
{
    for (int i = 0; i < items.Length; i++)
    {
        if (items[i] == target)
            return i;
    }
    return -1; // элемент не найден
}

Обратите внимание: вместо break здесь return. Когда поиск оформлен как отдельный метод, return и проще, и надёжнее — не нужна вспомогательная переменная foundIndex, и нет риска случайно выполнить код после цикла до проверки результата.

Но что если вам нужно найти не конкретное число, а элемент, который удовлетворяет какому-то условию? Скажем, первую цену выше 1000 рублей в каталоге товаров? Писать отдельный метод на каждое условие — не вариант. Тут на помощь приходят делегаты:

static int FindIndexByCondition(int[] prices, Func<int, bool> condition)
{
    for (int i = 0; i < prices.Length; i++)
    {
        if (condition(prices[i]))
            return i;
    }
    return -1;
}

// Использование:
int[] catalog = { 499, 750, 1200, 300, 1800 };
int idx = FindIndexByCondition(catalog, price => price > 1000);
Console.WriteLine(idx); // 2 (элемент 1200)

Мы передаём условие как делегат Func<int, bool> — функцию, которая принимает число и возвращает true или false. Метод по-прежнему идёт по массиву слева направо, но вместо сравнения с конкретным значением — вызывает переданную функцию. Этот приём делает поиск гибким: завтра вам понадобится найти первый отрицательный элемент — просто передадите другую лямбду, метод менять не нужно.

А если нужны все вхождения, а не только первое? Тогда вместо раннего выхода собираем результаты в список:

static List<int> FindAllIndices(int[] items, int target)
{
    var result = new List<int>();
    for (int i = 0; i < items.Length; i++)
    {
        if (items[i] == target)
            result.Add(i); // не break — продолжаем до конца
    }
    return result;
}

int[] data = { 7, 3, 7, 5, 7 };
List<int> indices = FindAllIndices(data, 7);
Console.WriteLine(string.Join(", ", indices)); // 0, 2, 4

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

Алгоритм простой. Но насколько он быстрый? Разберём это формально — через три классических сценария.

Вспомните нашу библиотеку. Если нужная книга стоит самой первой на полке — вы найдёте её мгновенно. Это лучший случай (best case): одно сравнение, O(1). Повезло.

Если книга стоит последней или её вообще нет — вы пройдёте все полки до конца. Это худший случай (worst case): n сравнений, O(n), где n — количество элементов. Не повезло.

А в среднем? Если элемент есть в массиве и с равной вероятностью может оказаться в любой позиции, то в среднем вы проверите половину массива — n/2 сравнений. Но в O-нотации константы отбрасываются, поэтому средний случай (average case) тоже O(n).

Что O(n) означает на практике. Для массива из 100 элементов — максимум 100 сравнений. Для 10 000 — десять тысяч. Современный компьютер выполняет миллиарды операций в секунду, так что для небольших массивов это мгновенно. Но вот для миллиона элементов, когда поиск вызывается тысячи раз в секунду (например, в поисковом движке или в базе данных), линейный поиск начинает ощутимо тормозить.

Вот простой способ прочувствовать разницу. Если в массиве 1 000 000 элементов, линейный поиск в худшем случае сделает 1 000 000 сравнений. Бинарный поиск (о нём — в следующем уроке) сделает всего 20. Не двадцать тысяч — ровно двадцать. Чувствуете масштаб?

Но не спешите хоронить линейный поиск. У него есть козырь: он не требует сортировки. Бинарный поиск работает только на упорядоченных данных. А сортировка массива — это O(n log n), что для одного поиска дороже, чем O(n). Получается парадокс: если нужно найти элемент один раз — линейный поиск выгоднее, чем «сортировка + бинарный поиск».

Когда же линейный поиск — хороший выбор? Вот три чётких критерия:

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

Второй — массив не отсортирован, и сортировать его ради одного-двух поисков нет смысла. Сортировка стоит O(n log n), сам поиск — O(n). Математика не в пользу сортировки.

Третий — вы ищете по сложному условию (не по равенству, а, скажем, «первый элемент больше среднего арифметического»). Более быстрые алгоритмы обычно требуют сортировки по ключу сравнения, а если условие произвольное — линейный обход неизбежен. C# — язык с богатой стандартной библиотекой, и вам не обязательно каждый раз писать цикл вручную. Посмотрим на встроенные инструменты, которые делают линейный поиск за вас, — и когда какой выбрать.

Array.IndexOf — классический поиск по значению. Самый близкий аналог нашего LinearSearch:

string[] cities = { "Москва", "Казань", "Сочи", "Казань" };
int index = Array.IndexOf(cities, "Казань");
Console.WriteLine(index); // 1 (первое вхождение)

Внутри — тот же линейный поиск. Метод возвращает -1, если элемент не найден. Работает для любого типа, у которого корректно определён Equals. Если в массиве несколько совпадений — вернёт индекс первого, точно так же как наш ручной цикл.

Array.Find — поиск по условию, возвращает сам элемент (не индекс). Это удобно, когда вам нужно не «где», а «что»:

int[] temperatures = { -5, 3, -12, 8, -1 };
int firstNegative = Array.Find(temperatures, t => t < 0);
Console.WriteLine(firstNegative); // -5

Если совпадений нет, Array.Find вернёт значение по умолчанию для типа: 0 для int, null для ссылочных типов. И вот тут кроется ловушка: если вы ищете в массиве чисел и получили 0 — это может означать и «не найдено», и «нашли ноль». Видите проблему? Поэтому для числовых массивов безопаснее использовать Array.FindIndex, который возвращает индекс (и понятный -1 при отсутствии).

LINQ-методы — ещё более выразительный способ. Вот три самых полезных для поиска:

using System.Linq;

string[] names = { "Алиса", "Борис", "Виктор", "Алиса" };

// Первый элемент по условию (или null, если не найден)
string? found = names.FirstOrDefault(n => n.StartsWith("Б"));
Console.WriteLine(found); // Борис

// Все элементы по условию
var allAlices = names.Where(n => n == "Алиса").ToList();
Console.WriteLine(allAlices.Count); // 2

// Проверка существования — без извлечения самого элемента
bool hasVictor = names.Any(n => n == "Виктор");
Console.WriteLine(hasVictor); // True

FirstOrDefault — находит первый подходящий элемент или возвращает null/default. Where — возвращает все подходящие элементы (аналог нашего FindAllIndices, но возвращает значения, а не индексы). Any — просто проверяет, есть ли хотя бы один подходящий элемент, и возвращает bool.

Все эти методы — линейный поиск под капотом. LINQ не делает магии: он прячет цикл за красивым синтаксисом. Сложность остаётся O(n). Но код становится гораздо читабельнее — вместо пяти строк с циклом вы пишете одну строку с понятным намерением.

Кстати, Array.IndexOf умеет искать не только с начала. У него есть перегрузка с указанием стартовой позиции:

string[] cities = { "Москва", "Казань", "Сочи", "Казань" };
int first = Array.IndexOf(cities, "Казань");       // 1
int second = Array.IndexOf(cities, "Казань", first + 1); // 3

Так можно пошагово находить все вхождения — каждый раз начиная поиск после предыдущей находки.

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

А что если справочник отсортирован по алфавиту? Тогда можно поступить умнее: открыть его посередине и сразу понять, нужная запись — в первой или второй половине. Потом разделить оставшуюся половину ещё раз пополам... Знакомая идея? Это бинарный поиск — тема следующего урока. Он работает за O(log n), что для миллиона элементов означает всего ~20 сравнений вместо миллиона.

Но прежде чем бежать к бинарному поиску — убедитесь, что вы уверенно владеете линейным. Он лежит в основе множества алгоритмов и встречается в реальном коде гораздо чаще, чем кажется. Каждый раз, когда вы пишете .Where(), .Any() или .FirstOrDefault() — за кулисами работает именно он.

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

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

Временная сложность — O(n) в среднем и худшем случае, O(1) в лучшем. Пространственная сложность — O(1).

Поиск первого вхождения — возвращает индекс и завершается через break/return. Поиск всех вхождений — проходит массив целиком, собирая результаты в список.

Поиск по условию — вместо сравнения с конкретным значением используется предикат (Func<T, bool>).

Встроенные методы C# — Array.IndexOf, Array.Find, Array.FindIndex, LINQ-методы FirstOrDefault, Where, Any — все выполняют линейный поиск под капотом.

Когда использовать — маленькие коллекции, несортированные данные, поиск по сложному условию.