Linear Search

Проблема

Быстрые способы поиска опираются на подготовку данных: бинарному поиску нужен отсортированный массив, хеш-таблице - заранее построенный индекс. Если данные не упорядочены, приходят потоком или искать нужно один раз, такая подготовка стоит дороже самого поиска. Нужен способ, который работает с любой последовательностью как она есть.

Решение

Идём по массиву слева направо и сравниваем каждый элемент с искомым. Совпало - возвращаем индекс, и это первое вхождение. Дошли до конца без совпадения - возвращаем -1. В обычном цикле на каждом шаге две проверки: не кончился ли массив и не тот ли это элемент. Вариант с барьером (sentinel) кладёт искомое значение в конец массива, и цикл гарантированно остановится на нём, поэтому проверка границы внутри цикла больше не нужна.

Как это работает

Линейный поиск - точка отсчёта для всех остальных алгоритмов поиска: он смотрит элементы по очереди и ничего не знает о данных заранее. Лучший случай - одно сравнение, если искомое стоит первым. Худший - n сравнений, если оно последнее или его нет. Если каждый элемент ищут одинаково часто, удачный поиск в среднем стоит (n + 1) / 2 сравнений: для массива из 9 элементов это ровно 5.

В обычном цикле на каждом шаге две проверки: i < arr.length и arr[i] === target. Кнут в третьем томе «Искусства программирования» (§6.1) описывает приём, который убирает первую: барьер (sentinel, Algorithm Q). Искомое значение ставят в конец массива, и цикл гарантированно на нём остановится. После цикла остаётся одна проверка: остановились на настоящем элементе или на барьере.

У барьера две цены. Первая - массив на время меняется: так нельзя искать в замороженном массиве, в данных, которые одновременно читает другой код, или там, где в конец просто нечего дописать. Вторая - барьер работает, только если искомое равно самому себе. Для NaN это неверно: в JS цикл без защиты не останавливается (проверка с ограничителем дошла до миллиона шагов), а в Python падает с IndexError за концом списка. Поэтому в примере стоит отдельная проверка на NaN.

Если массив отсортирован, линейный поиск может бросить работу раньше: как только текущий элемент больше искомого, дальше его быть не может. У Кнута это отдельный вариант для упорядоченной таблицы (Algorithm T). Отсутствующий элемент находится быстрее, но в худшем случае это всё равно O(n). Порядок можно использовать гораздо сильнее - каждое сравнение отбрасывает половину массива, и это уже бинарный поиск.

Когда одни элементы ищут гораздо чаще других, их выгодно держать ближе к началу. Самоорганизующиеся списки делают это сами: найденный элемент переносят в начало (move-to-front) или меняют местами с предыдущим (transpose). Порядок подстраивается под реальные запросы, и частые поиски становятся короткими, хотя худший случай остаётся O(n).

Встроенные функции поиска в языках - тоже линейный поиск, но с разным понятием равенства. В JS indexOf сравнивает строгим равенством, а includes - через SameValueZero, поэтому [1, 2, NaN].indexOf(NaN) даёт -1, а includes(NaN) - true. В CPython оператор in перед сравнением проверяет, тот же ли это объект: nan in [nan] даёт True, а float('nan') in [nan] - False, потому что это другой объект NaN.

Страница O(n) - Линейная Сложность в разделе Big O использует ту же функцию как пример класса сложности; здесь речь о самом алгоритме - его вариантах и ловушках. Линейный поиск проигрывает, когда искать приходится много раз: тогда один раз отсортировать массив и искать бинарным поиском или построить Set/Map выгоднее, чем каждый раз проходить всё. Но для одного поиска в несортированных данных подготовка дороже самого поиска, и линейный поиск остаётся лучшим выбором.

Нюансы выбора

Один поиск в несортированных данных - сортировка ради одного поиска стоит O(n log n), а сам линейный поиск - не больше n сравнений. Подготовка не окупится.

Нет доступа по индексу - в связном списке, потоке или генераторе к середине не прыгнуть, поэтому бинарный поиск невозможен, а линейный работает как есть.

Много поисков - если по одним данным ищут снова и снова, лучше один раз отсортировать и искать бинарным поиском или сложить значения в Set/Map и проверять за O(1) в среднем.

Неравные вероятности - если часть элементов ищут гораздо чаще, их ставят в начало, вручную или самоорганизующимся списком (move-to-front, transpose).

Барьер - только где можно менять массив - вариант с барьером требует временной записи в конец и значения, равного самому себе. Замороженные и общие массивы и поиск NaN ему не подходят.

Примеры в коде

Donald Knuth, «The Art of Computer Programming», т. 3 «Sorting and Searching», §6.1 «Sequential Searching» - последовательный поиск, вариант с барьером (Algorithm Q) и вариант для упорядоченной таблицы (Algorithm T).

Строки в C - строка заканчивается нулевым байтом '\0', и strlen идёт по символам, пока его не встретит. Это тот же барьер: длину строки нигде не хранят, конец отмечен значением.

CPython, сравнение объектов - функция PyObject_RichCompareBool в Objects/object.c перед сравнением на равенство проверяет, не один ли это объект, и если один, сразу отвечает «равны». Поэтому in и list.index находят тот же самый объект NaN.

MDN о методе includes - страница Array.prototype.includes описывает сравнение SameValueZero: как строгое равенство, только NaN считается равным самому себе, а -0 и +0 - равными друг другу.

Когда применять

• Когда данные не отсортированы, а искать нужно один или несколько раз: сортировка ради одного поиска стоит O(n log n), а сам поиск - n сравнений.
• Когда к элементам нельзя обратиться по индексу - поток, связный список, генератор - или когда массив маленький.

Примеры из практики

• Методы массива в JavaScript - indexOf, includes и find идут по элементам по порядку. indexOf сравнивает строгим равенством и NaN не находит, а includes использует сравнение SameValueZero, где NaN равен себе: [1, 2, NaN].indexOf(NaN) даёт -1, а includes(NaN) - true.
• Поиск в списках Python - оператор in и метод list.index в CPython - простые циклы в Objects/listobject.c (list_contains, list_index_impl). Если значения нет, list.index выбрасывает ValueError, а не возвращает -1.