Линейный поиск

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

Идея алгоритма

Пусть есть массив $a$ из $n$ элементов и число $x$, которое нужно найти.

1. Смотрим на первый элемент. Если он равен $x$ — поиск окончен, ответ — его номер.
2. Иначе переходим к следующему элементу.
3. Если дошли до конца массива и ничего не нашли — элемента в массиве нет.

Ключевая идея: Линейный поиск не требует, чтобы массив был отсортирован. Это его главное преимущество перед бинарным поиском — и единственное.

Код

def linear_search(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i      # нашли: возвращаем индекс
    return -1             # прошли весь массив, элемента нет


print(linear_search([7, 3, 9, 3, 5], 9))   # 2
print(linear_search([7, 3, 9, 3, 5], 4))   # -1

Та же идея на C++:

#include <iostream>
#include <vector>

int linearSearch(const std::vector<int>& a, int x) {
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] == x) return i;
    }
    return -1;
}

int main() {
    std::vector<int> a = {7, 3, 9, 3, 5};
    std::cout << linearSearch(a, 9) << "\n";   // 2
    std::cout << linearSearch(a, 4) << "\n";   // -1
}

Функция возвращает индекс первого найденного элемента. Если нужны все вхождения, вместо return внутри цикла добавляй индекс в список и продолжай перебор.

Совет: В Python для проверки «есть ли элемент» достаточно написать x in a, а индекс даёт a.index(x). Внутри оба делают тот же линейный перебор.

Сколько шагов

В лучшем случае искомый элемент стоит первым — одно сравнение. В худшем случае элемент последний или его нет вовсе — $n$ сравнений. В среднем, если элемент есть и все позиции равновероятны, — около $\frac{n}{2}$ сравнений. Говорят, что линейный поиск работает за $O(n)$: время растёт пропорционально размеру массива.

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

Когда какой поиск выбирать

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

Частая ошибка: Частая ошибка на олимпиадах: линейный поиск внутри цикла. Если для каждого из $n$ запросов перебирать массив из $n$ элементов, получится $n^2$ операций — при $n = 10^5$ это уже $10^{10}$, и решение не уложится в лимит времени.

Заметка: Если заранее известно, что элемент в массиве есть, проверку «не вышли ли за край» можно убрать: временно дописать $x$ в конец массива и перебирать, пока не встретится $x$. Такой приём называют поиском с барьером.