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

Введение

Предположим, нам дан массив

a_1, a_2, \ldots, a_n

и значение $x$ .

Нам нужно найти индекс такой, что

i

i

a_i = x

или определить, что такого индекса не существует.

Алгоритм

Простой способ решить эту задачу — линейный поиск.

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

В худшем случае нам может понадобиться проверить все элементы, поэтому временная сложность:

O(n)

Линейный поиск можно реализовать с помощью цикла for или цикла while.

Цикл For

Цикл While

int Search(const vector<int>& a, int x) {
    for (size_t i = 0; i < a.size(); i++) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1; // not found
}

int Search(const vector<int>& a, int x) {
    size_t i = 0;
    while (i < a.size() && a[i] != x) {
        i += 1;
    }
    if (i == a.size()) {
        return -1;
    }
    return i;
}