Линейный поиск
Самый простой способ что-то найти: идти по элементам по очереди и сравнивать с нужным значением.
Идея алгоритма
Представь, что у тебя есть список чисел или имён, и ты ищешь одно конкретное. Линейный поиск просто проходит по списку слева направо и сравнивает каждый элемент с тем, что мы ищем. Если нашли — возвращаем позицию; если дошли до конца и не нашли — говорим, что элемента нет.
Асимптотика:
- Время (худший / средний случай): O(n)
- Время (лучший случай — элемент стоит первым): O(1)
- Память: O(1)
Плюсы
- Очень простой для понимания и реализации;
- Работает на любом массиве, не требует сортировки;
- Можно использовать даже для сложных объектов (по условию).
Минусы
- Медленно на больших массивах;
- В худшем случае придётся посмотреть каждый элемент;
- Проигрывает более умным алгоритмам, если данные отсортированы.
Пример кода
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // нашли индекс
}
}
return -1; // не нашли
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания