Линейный поиск
Проще некуда: проверяем элементы по очереди, пока не найдём нужный.
1function linearSearch(arr: number[], target: number): number {2 for (let i = 0; i < arr.length; i++) {3 if (arr[i] === target) return i4 }5 return -16}Проблема
Найти значение в массиве, про который ничего не известно: не отсортирован, никакой структуры. Единственный честный способ — посмотреть каждый элемент, пока не встретим цель.
Что вы видите
Массив — полка, указатель i — палец, которым ведём слева направо. Проверенная и не подошедшая ячейка гаснет. Если цель нашлась — ячейка вспыхивает фиолетовым.
Как это работает
Линейный поиск не требует ни сортировки, ни подготовки и на маленьких массивах быстрее константных накладных расходов «умных» методов. Но его стоимость линейна: миллион элементов — до миллиона проверок. Именно поэтому отсортированные данные переводят на бинарный поиск.
Пошаговый разбор
- 01
Старт
i = 0: смотрим на первый элемент.
- 02
Сравнение
arr[i] равен цели? Да — ответ найден.
- 03
Шаг вправо
Нет — гасим ячейку и сдвигаем i.
- 04
Конец массива
Дошли до конца без совпадения — значения нет.
Complexity и ограничения
Работает на любых данных. Лучший случай O(1), худший O(n).
Edge cases
- Пустой массив
Цикл не выполнится ни разу, вернём -1.
- Цель — первый элемент
Одно сравнение, O(1).
- Несколько вхождений
Вернётся первое по порядку.
Где встречается в реальности
Малые массивы
До десятков элементов линейный поиск быстрее бинарного из-за отсутствия накладных расходов.
Неотсортированные данные
Единственный вариант, когда о порядке ничего не известно.
find/indexOf
Методы массивов в JS внутри — линейный поиск.
Связанные алгоритмы
«Почему «тупой» поиск иногда быстрее умного?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.