Алгоритмы поиска на JavaScript

Задача поиска связана с нахождением заданного значения, называемого ключом поиска (search key), среди заданного множества. Существует огромное количество алгоритмов поиска, так что есть из чего выбирать. Их сложность варьируется от самых простых алгоритмов поиска методом последовательного сравнения, до чрезвычайно эффективных, но ограниченных алгоритмов бинарного поиска, а также алгоритмов, основанных на представлении базового множества в иной, более подходящей для выполнения поиска форме. Последние из упомянутых здесь алгоритмов имеют особое практическое значение, поскольку применяются в реально действующих приложениях, выполняющих выборку и хранение массивов информации в огромных базах данных.

Для решения задачи поиска также не существует единого алгоритма, который бы наилучшим образом подходил для всех случаев. Некоторые из алгоритмов выполняются быстрее остальных, но для их работы требуется дополнительная оперативная память. Другие выполняются очень быстро, но их можно применять только для предварительно отсортированных массивов, и т.п. В отличие от алгоритмов сортировки в алгоритмах поиска нет проблемы устойчивости, но при их использовании могут возникать другие сложности. В частности, в тех приложениях, где обрабатываемые данные могут часто изменяться, причем количество изменений сравнимо с количеством операций поиска, поиск следует рассматривать в неразрывной связи с двумя другими операциями — добавления элемента в набор данных и удаления из него. В подобных ситуациях необходимо видоизменить структуры данных и алгоритмы так, чтобы достигалось равновесие между требованиями, выдвигаемыми к каждой операции. Кроме того, организация очень больших наборов данных с целью выполнения в них эффективного поиска (а также добавления и удаления элементов) представляет собой чрезвычайно сложную задачу, решение которой особенно важно с точки зрения практического применения.

Алгоритм линейного поиска (linear search) просто по очереди сравнивает элементы заданного списка с ключом поиска до тех пор, пока не будет найден элемент с указанным значением ключа (успешный поиск) или весь список будет проверен, но требуемый элемент не найден (неудачный поиск). Зачастую применяется простой дополнительный прием: если добавить ключ поиска в конец списка, то поиск обязательно будет успешным, следовательно, можно убрать проверку завершения списка в каждой итерации алгоритма. Далее приведен код реализации данного алгоритма на JavaScript; предполагается, что входные данные имеют вид массива.

function LinearSearch(t, A)     // t - искомый элемент,
{                               // A - массив, в котором ищем.
    var n = A.length,
        i = 0;

    A[n] = t;

    while (A[i] !== t) i++;

    if (i < n) return i;        // На выходе индекс искомого элемента.
    else return -1;             // Если искомого элемента нет в массиве, то -1.
}

Поиск элемента в отсортированном массиве. Бинарный поиск (binary search) представляет собой в высшей степени эффективный алгоритм для поиска в отсортированном массиве. Он работает путем сравнения искомого ключа \( t \) со средним элементом массива \( A[k] \) Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если \( t < A[k] \), и для второй, если \( t> A[k] \).

Стандартная реализация алгоритма бинарного поиска на JavaScript

function BinarySearch(t, A)         // t - искомый элемент,
{                                   // A - упорядоченный массив, в котором ищем.
    var i = 0,
        j = A.length - 1,
        k;

    while (i <= j) {
        k = Math.floor((i + j) / 2);
        if (t === A[k]) return k;
        else if (t < A[k]) j = k - 1;
        else i = k + 1;
    }
                                    // На выходе индекс искомого элемента.
    return -1;                      // Если искомого элемента нет в массиве, то -1.
}

Оптимизированный вариант

function BinarySearch(t, A)         // t - искомый элемент,
{                                   // A - упорядоченный массив, в котором ищем.
    var i = 0,
        j = A.length,
        k;

    while (i < j) {
        k = Math.floor((i + j) / 2);
        if (t <= A[k]) j = k;
        else i = k + 1;
    }

    if (A[i] === t) return i;       // На выходе индекс искомого элемента.
    else return -1;                 // Если искомого элемента нет в массиве, то -1.
}

Рассмотрим алгоритм поиска в отсортированном массиве, который называется интерполирующим поиском (interpolation search). В отличие от бинарного поиска, который всегда сравнивает ключ поиска со средним значением отсортированного массива (а следовательно, всегда уменьшает размер задачи вдвое), интерполяционный поиск учитывает значение ключа поиска при определении элемента массива, который будет сравниваться с ключом. В определенном смысле алгоритм имитирует поиск имени в телефонной книге. Если мы ищем в телефонной книге, например, Иванов — вряд ли мы будем открывать ее в средине или ближе к концу, как поступили бы при поиске Петрова.

function InterpolationSearch(t, A)          // t - искомый элемент,
{                                           // A - упорядоченный массив, в котором ищем.
    var mid, low = 0,
        high = A.length - 1;

    while (A[low] < t && A[high] > t) {
        mid = low + Math.floor(((t - A[low]) * (high - low)) / (A[high] - A[low]));
        if (A[mid] < t) low = mid + 1;
        else if (A[mid] > t) high = mid - 1;
        else return mid;
    }

    if (A[low] === t) return low;           // На выходе индекс искомого элемента.
    else if (A[high] === t) return high;    // Если искомого элемента нет в массиве, то -1.
    else return -1;
}

Формально задачу поиска подстроки (substring search) можно сформулировать следующим образом. Пусть есть некоторый текст \( \mathsf{str} \) символов с длиной \( N \) , и шаблон \( \mathsf{sub} \) с длиной \( n~ (n\leqslant N) \) в виде строки. Если для некоторого значения \( i\in[0;N-n+1) \) выполняется равенство \( \mathsf{str}[ i],\ldots,\mathsf{str}[i+n-1]= \mathsf{sub}[0],\ldots,\mathsf{sub}[n-1] \) , т.е. если для всех \( j\in[0;n) \) справедливо равенство \( \mathsf{sub}[j]=\mathsf{str}[i+j] \), то будем говорить, что шаблон \( \mathsf{sub} \) входит в текст \( \mathsf{str} \) со сдвигом \( i \) . Задача поиска подстроки состоит в определении сдвига, с которым шаблон \( \mathsf{sub} \) входит в текст \( \mathsf{str} \) (или установлении того факта, что текст не содержит подстроки, соответствующей шаблону). Проще говоря, нужно определить индекс \( i \) крайнего слева символа первой соответствующей шаблону \( \mathsf{sub} \) подстроки в тексте \( \mathsf{str} \)

(например, если str = "Lorem ipsum" и sub = "ips", то \( i=6 \) ).

Простейший алгоритм поиска состоит в непосредственной проверке всех возможных смещений. Проверка заключается в последовательном сравнении символов шаблона \( \mathsf{sub} \) с символами строки \( \mathsf{str} \) ; при первом же обнаруженном несовпадении символов проверка прекращается и переменная внешнего цикла увеличивается на 1.

function SubstringSearch(sub, str)    // sub - искомая подстрока
{                                     // str - строка, в которой ищем
    var i, j, n = sub.length,
        N = str.length - n + 1;

    for (i = 0; i < N; i++)
    {  j = 0;
       while (j < n && sub.charAt(j) === str.charAt(i+j)) j++;
       if (j === n) return i;
    }                                // На выходе индекс 1-го символа подстроки.
                                     // Если искомой подстроки нет в строке, то -1.
    return -1;                       // Например,
}                                    // SubstringSearch('ips', 'Lorem ipsum') = 6,
                                     // SubstringSearch('dolor', 'Lorem ipsum') = -1.