Алгоритмы для поиска

Линейный поиск

Алгоритм ищет элемент в заданной структуре данных, пока не достигнет конца структуры.

Временная сложность - O(N).

1
2
3
4
5
6
7
8
public static int linearSearch(int arr[], int elementToSearch) {

    for (int index = 0; index < arr.length; index++) {
        if (arr[index] == elementToSearch)
            return index;
    }
    return -1;
}

Двоичный поиск

Алгоритм делит входную коллекцию на равные половины, и с каждой итерацией сравнивает целевой элемент с элементом в середине. Поиск заканчивается при нахождении элемента. Иначе продолжаем искать элемент, разделяя и выбирая соответствующий раздел массива. Целевой элемент сравнивается со средним.

Временная сложность - O(log (N)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static int binarySearch(int arr[], int elementToSearch) {

    int firstIndex = 0;
    int lastIndex = arr.length - 1;

    // условие прекращения (элемент не представлен)
    while(firstIndex <= lastIndex) {
        int middleIndex = (firstIndex + lastIndex) / 2;
        // если средний элемент - целевой элемент, вернуть его индекс
        if (arr[middleIndex] == elementToSearch) {
            return middleIndex;
        }

        // если средний элемент меньше
        // направляем наш индекс в middle+1, убирая первую часть из рассмотрения
        else if (arr[middleIndex] < elementToSearch)
            firstIndex = middleIndex + 1;

        // если средний элемент больше
        // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения
        else if (arr[middleIndex] > elementToSearch)
            lastIndex = middleIndex - 1;

    }
    return -1;
}

public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {

    // условие прекращения
    if (lastElement >= firstElement) {
        int mid = firstElement + (lastElement - firstElement) / 2;

        // если средний элемент - целевой элемент, вернуть его индекс
        if (arr[mid] == elementToSearch)
            return mid;

        // если средний элемент больше целевого
        // вызываем метод рекурсивно по суженным данным
        if (arr[mid] > elementToSearch)
            return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);

        // также, вызываем метод рекурсивно по суженным данным
        return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);
    }

    return -1;
}

Алгоритм Кнута – Морриса – Пратта

Cначала компилируется заданный шаблон. Компилируя шаблон, мы пытаемся найти префикс и суффикс строки шаблона. Это поможет в случае несоответствия – не придётся искать следующее совпадение с начального индекса.

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

Временная сложность - O (M + N)

Поиск прыжками

От двоичного поиска этот алгоритм отличает движение исключительно вперёд.
Прыгаем вперёд на интервал sqrt(arraylength), пока не достигнем элемента большего, чем текущий элемент или конца массива. При каждом прыжке записывается предыдущий шаг.
Прыжки прекращаются, когда найден элемент больше искомого. Затем запускаем линейный поиск между предыдущим и текущим шагами.

Временная сложность - O(sqrt (N))

Интерполяционный поиск

При равномерно распределенных данных местонахождение элемента определяется точнее. Тут и вскрывается отличие алгоритма от бинарного поиска, где мы пытаемся найти элемент в середине массива.
Для поиска элементов в массиве алгоритм использует формулы интерполяции. Эффективнее применять эти формула для больших массивов. В противном случае алгоритм работает как линейный поиск.

Временная сложность - O(log log N).

Экспоненциальный поиск

Пытаемся найти сравнительно меньший диапазон и применяем на нем двоичный алгоритм для поиска элемента.
Для работы алгоритма коллекция должна быть отсортирована.

Временная сложность - O(log (N)).

https://proglib.io/p/6-search-algorithms-java