Введение
Предположим, нам дан массив
и значение .
Нам нужно найти индекс такой, что
Предположим, нам дан массив
и значение .
Нам нужно найти индекс такой, что
или определить, что такого индекса не существует.
Простой способ решить эту задачу — линейный поиск.
Идея проста: мы просматриваем массив слева направо и сравниваем каждый элемент с , пока либо не найдём требуемое значение, либо не дойдём до конца массива.
В худшем случае нам может понадобиться проверить все элементы, поэтому временная сложность:
Линейный поиск можно реализовать с помощью цикла 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;
}