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

Автор оригинала: Chandan Singh.

Вступление

Поиск-одно из наиболее распространенных действий, выполняемых в обычных бизнес-приложениях. Это включает в себя извлечение некоторых данных, хранящихся в структурах данных, таких как Массивы , Список , Карта и т.д. Чаще всего эта операция поиска определяет скорость отклика приложения для конечного пользователя.

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

• Линейный Поиск
• Двоичный поиск
• Поиск шаблонов Кнута Морриса Пратта
• Поиск прыжков
• Интерполяционный поиск
• Экспоненциальный поиск
• Поиск Фибоначчи
• API коллекций Java

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

Линейный или последовательный поиск является самым простым из алгоритмов поиска. Хотя это, безусловно, самое простое, оно определенно не самое распространенное из-за его неэффективности. Это алгоритм грубой силы. Очень редко он используется в производстве, и в большинстве случаев он превосходит другие алгоритмы.

Линейный поиск не имеет предпосылок для состояния базовой структуры данных.

Объяснение

Линейный поиск включает последовательный поиск элемента в данной структуре данных до тех пор, пока либо элемент не будет найден, либо не будет достигнут конец структуры.

Если элемент найден, мы обычно просто возвращаем его положение в структуре данных. Если нет, мы обычно возвращаемся -1 .

Реализация

Теперь давайте посмотрим, как реализовать линейный поиск в Java:

public static int linearSearch(int arr[], int elementToSearch) {

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

Чтобы проверить это, мы будем использовать простой массив целых чисел:

int index = linearSearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);

С помощью простого вспомогательного метода для печати результата:

public static void print(int elementToSearch, int index) {
    if (index == -1){
        System.out.println(elementToSearch + " not found.");
    }
    else {
        System.out.println(elementToSearch + " found at index: " + index);
    }
}

Выход:

67 found at index: 8

Временная Сложность

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

В этом случае мы повторим N раз, прежде чем найдем элемент.

Следовательно, временная сложность линейного поиска равна O(N) .

Сложность Пространства

Для этого типа поиска требуется только одна единица памяти для хранения искомого элемента. Это не имеет отношения к размеру входного массива.

Следовательно, пространственная сложность линейного поиска равна O(1) .

Приложения

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

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

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

Двоичный или логарифмический поиск является одним из наиболее часто используемых алгоритмов поиска, в первую очередь из-за его быстрого времени поиска.

Объяснение

Этот вид поиска использует методологию Разделяй и властвуй и требует предварительной сортировки набора данных.

Он делит входную коллекцию на равные половины и с каждой итерацией сравнивает элемент цели с элементом посередине.

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

Вот почему важно иметь отсортированную коллекцию для двоичного поиска.

Поиск завершается, когда первый индекс (или указатель) проходит мимо последнего индекса (последнего элемента), что означает, что мы искали весь массив, а элемента нет.

Существует два способа реализации этого алгоритма – итеративный и рекурсивный .

Между этими двумя реализациями не должно быть разницы во времени и сложности пространства, хотя это справедливо не для всех языков.

Реализация

Повторяющийся

Давайте сначала взглянем на итеративный подход:

public static int binarySearch(int arr[], int elementToSearch) {

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

    // termination condition (element isn't present)
    while(firstIndex <= lastIndex) {
        int middleIndex = (firstIndex + lastIndex) / 2;
        // if the middle element is our goal element, return its index
        if (arr[middleIndex] == elementToSearch) {
            return middleIndex;
        }

        // if the middle element is smaller
        // point our index to the middle+1, taking the first half out of consideration
        else if (arr[middleIndex] < elementToSearch)
            firstIndex = middleIndex + 1;

        // if the middle element is bigger
        // point our index to the middle-1, taking the second half out of consideration
        else if (arr[middleIndex] > elementToSearch)
            lastIndex = middleIndex - 1;

    }
    return -1;
}

Мы можем использовать алгоритм следующим образом:

int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);

Выход:

67 found at index: 5

Рекурсивный

А теперь давайте взглянем на рекурсивную реализацию:

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

    // termination condition
    if (lastElement >= firstElement) {
        int mid = firstElement + (lastElement - firstElement) / 2;

        // if the middle element is our goal element, return its index
        if (arr[mid] == elementToSearch)
            return mid;

        // if the middle element is bigger than the goal element
        // recursively call the method with narrowed data
        if (arr[mid] > elementToSearch)
            return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);

        // else, recursively call the method with narrowed data
        return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);
    }

    return -1;
}

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

Другое отличие здесь заключается в том, что рекурсивные вызовы помещаются в стек вызовов методов и занимают одну единицу пространства на рекурсивный вызов.

Мы можем использовать этот алгоритм следующим образом:

int index = binarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67);
print(67, index);

Выход:

67 found at index: 5

Временная Сложность

Поскольку двоичный поиск каждый раз делит массив пополам, его временная сложность составляет O(log(N)) . Эта временная сложность является заметным улучшением O(N) временной сложности линейного поиска.

Сложность Пространства

Для этого поиска требуется только одна единица пространства для хранения элемента, подлежащего поиску. Следовательно, его пространственная сложность равна O(1) .

Если двоичный поиск реализован рекурсивно, ему необходимо сохранить вызов метода в стеке. Для этого может потребоваться O(log(N)) пространство в худшем случае.

Приложения

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

Двоичный поиск также реализован в API Java в методе Arrays.BinarySearch .

Поиск шаблонов Кнута Морриса Пратта

Как следует из названия, это алгоритм поиска шаблона в данном тексте. Этот алгоритм был разработан Дональдом Кнутом, Воаном Праттом и Джеймсом Моррисом, отсюда и название.

Объяснение

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

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

В результате этого пропуска мы можем сэкономить много сравнений, и KMP работает быстрее, чем наивный алгоритм грубой силы.

Реализация

Давайте создадим метод compile Pattern Array () , который позже будет использоваться алгоритмом поиска KMP:

public static int[] compilePatternArray(String pattern) {
    int patternLength = pattern.length();
    int len = 0;
    int i = 1;
    int[] compliedPatternArray = new int[patternLength];
    compliedPatternArray[0] = 0;

    while (i < patternLength) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            compliedPatternArray[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = compliedPatternArray[len - 1];
            } else {
                compliedPatternArray[i] = len;
                i++;
            }
        }
    }
    System.out.println("Compiled Pattern Array " + Arrays.toString(compliedPatternArray));
    return compliedPatternArray;
}

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

Скомпилированный массив хранит позицию индекса предыдущего вхождения текущего символа в массиве шаблонов.

Давайте реализуем сам алгоритм:

public static List performKMPSearch(String text, String pattern) {
    int[] compliedPatternArray = compilePatternArray(pattern);

    int textIndex = 0;
    int patternIndex = 0;

    List foundIndexes = new ArrayList<>();

    while (textIndex < text.length()) {
        if (pattern.charAt(patternIndex) == text.charAt(textIndex)) {
            patternIndex++;
            textIndex++;
        }
        if (patternIndex == pattern.length()) {
            foundIndexes.add(textIndex - patternIndex);
            patternIndex = compliedPatternArray[patternIndex - 1];
        }

        else if (textIndex < text.length() && pattern.charAt(patternIndex) != text.charAt(textIndex)) {
            if (patternIndex != 0)
                patternIndex = compliedPatternArray[patternIndex - 1];
            else
                textIndex = textIndex + 1;
        }
    }
    return foundIndexes;
}

Здесь мы начнем с последовательного сравнения символов в шаблоне и текстовом массиве. Мы продолжаем двигаться вперед, пока не получим совпадение шаблонов и текстовых массивов. Таким образом, если мы достигнем конца массива шаблонов при сопоставлении, это означает, что мы нашли вхождение шаблона в текст.

Однако, если мы обнаружим несоответствие при сравнении двух массивов, мы переместим индекс массива символов шаблона в значение в compiledPatternArray () , а также перейдем к следующему символу в текстовом массиве. Именно здесь поиск KMP превосходит подход грубой силы, поскольку он не сравнивает текстовые символы более одного раза, если есть несоответствие.

Давайте попробуем запустить алгоритм:

String pattern = "AAABAAA";
String text = "ASBNSAAAAAABAAAAABAAAAAGAHUHDJKDDKSHAAJF";

List foundIndexes = KnuthMorrisPrathPatternSearch.performKMPSearch(text, pattern);

if (foundIndexes.isEmpty()) {
    System.out.println("Pattern not found in the given text String");
} else {
    System.out.println("Pattern found in the given text String at positions: " + .stream().map(Object::toString).collect(Collectors.joining(", ")));
}

В тексте шаблона ААААААА наблюдается и кодируется в массиве шаблонов следующий шаблон:

• Шаблон A (Один A) повторяется в индексе 1 и снова в 4.
• Шаблон AA (Двойной A) повторяется в индексе 2 и снова в индексе 5.
• Шаблон AAA (3 А) повторяется при индексе 6.

Давайте посмотрим на результаты, чтобы подтвердить нашу дискуссию до сих пор:

Compiled Pattern Array [0, 1, 2, 0, 1, 2, 3]
Pattern found in the given text String at positions: 8, 14

Описанный нами шаблон четко показан нам в скомпилированном массиве шаблонов на выходе.

С помощью этого скомпилированного массива алгоритм поиска KMP может искать заданный шаблон в тексте, не возвращаясь в текстовый массив.

Временная Сложность

Этот алгоритм должен сравнить все элементы в данном тексте, чтобы найти шаблон. Время, необходимое для этого, составляет O(N) . Для компиляции строки шаблона нам нужно посетить каждый символ в шаблоне, и это еще одна O(M) итерация.

Таким образом, общее время, затрачиваемое этим алгоритмом, составит O(M+N) .

Сложность Пространства

Нам нужно O(M) пространство для хранения скомпилированного шаблона для заданного шаблона размера M

Приложения

Этот алгоритм особенно используется в текстовых инструментах для поиска шаблонов в текстовых файлах.

Поиск прыжков

Объяснение

Этот поиск похож на двоичный поиск, но вместо того, чтобы прыгать как вперед, так и назад – мы будем прыгать только вперед. Имейте в виду, что Поиск перехода также требует сортировки коллекции.

В поиске переходов мы переходим в интервал sqrt(длина массива) вперед, пока не достигнем элемента, превышающего текущий элемент или конец массива. При каждом прыжке записывается предыдущий шаг.

Если мы сталкиваемся с элементом, большим, чем элемент, который мы ищем, мы перестаем прыгать. Затем мы выполняем линейный поиск между предыдущим шагом и текущим шагом.

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

Реализация

public static int jumpSearch(int[] integers, int elementToSearch) {

    int arrayLength = integers.length;
    int jumpStep = (int) Math.sqrt(integers.length);
    int previousStep = 0;

    while (integers[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) {
        previousStep = jumpStep;
        jumpStep += (int)(Math.sqrt(arrayLength));
        if (previousStep >= arrayLength)
            return -1;
    }
    while (integers[previousStep] < elementToSearch) {
        previousStep++;
        if (previousStep == Math.min(jumpStep, arrayLength))
            return -1;
    }

    if (integers[previousStep] == elementToSearch)
        return previousStep;
    return -1;
}

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

Поэтому мы сначала посещаем элемент в целые числа[шаг перехода] , затем целые числа[2 шага перехода] , целые числа[3 шага перехода] и так далее. Мы также сохраняем предыдущий посещенный элемент в переменной предыдущий шаг .

Как только мы найдем значение , такое, что целые числа[предыдущий шаг] < Поиск элементов < целые числа[Шаг перехода] , мы выполняем линейный поиск между целыми числами[предыдущий шаг] и целыми числами[Шаг перехода] или элементом, большим, чем Поиск элементов .

Мы можем использовать алгоритм следующим образом:

int index = jumpSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Выход:

67 found at Index 5

Временная Сложность

Поскольку мы переходим sqrt(длина массива) шагов на каждой итерации, временная сложность для этого поиска составляет O(sqrt(N)) .

Сложность Пространства

Сложность пространства для этого поиска составляет O(1) , поскольку для хранения элемента, подлежащего поиску, требуется только одна единица пространства.

Приложение

Этот поиск используется поверх двоичного поиска, когда возврат назад обходится дорого. Это ограничение возникает, когда мы используем вращающиеся носители, такие как диски, когда легко двигаться вперед, но многократно прыгать в измененном направлении дорого.

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

Объяснение

Интерполяционный поиск используется для поиска элементов в отсортированном массиве. Этот поиск особенно полезен, если мы знаем, что данные в базовой структуре распределены равномерно.

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

Интерполяционный поиск использует интерполяционные формулы для поиска наиболее вероятного места, где элемент может быть найден в массиве. Однако для того, чтобы эти формулы были эффективными, массив поиска должен быть большим, в противном случае он выполняется как линейный поиск:

Реализация

public static int interpolationSearch(int[] integers, int elementToSearch) {

    int startIndex = 0;
    int lastIndex = (integers.length - 1);

    while ((startIndex <= lastIndex) && (elementToSearch >= integers[startIndex]) &&
           (elementToSearch <= integers[lastIndex])) {
        // using interpolation formulae to find the best probable position for this element to exist
        int pos = startIndex + (((lastIndex-startIndex) /
          (integers[lastIndex]-integers[startIndex]))*
                        (elementToSearch - integers[startIndex]));

        if (integers[pos] == elementToSearch)
            return pos;

        if (integers[pos] < elementToSearch)
            startIndex = pos + 1;

        else
            lastIndex = pos - 1;
    }
    return -1;
}

Мы можем использовать этот алгоритм следующим образом:

int index = interpolationSearch(new int[]{1,2,3,4,5,6,7,8}, 6);
print(67, index);

Выход:

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

6 found at Index 5

Давайте взглянем на то, как формулы интерполяции творят свое волшебство, чтобы искать 6 :

startIndex = 0
lastIndex = 7
integers[lastIndex] = 8
integers[startIndex] = 1
elementToSearch = 6

Теперь давайте применим эти значения к формулам для оценки индекса поискового элемента:

$$ + $$

Элемент в целых числах[5] равен 6, что является элементом, который мы искали. Как мы видим здесь, индекс для элемента рассчитывается всего за один шаг, так как данные распределены равномерно.

Временная Сложность

В лучшем случае временная сложность для этого алгоритма составляет O(log log N) , но в худшем случае, т. е. когда элементы распределены неравномерно, она сопоставима со сложностью линейного поиска, которая составляет O(N) .

Сложность Пространства

Этот алгоритм также требует только одной единицы пространства для хранения элемента, подлежащего поиску. Следовательно, его пространственная сложность равна O(1) .

Приложение

Этот поиск полезен, когда данные равномерно распределены, как телефонные номера в справочнике.

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

Объяснение

Экспоненциальный поиск используется для поиска элементов путем перехода в экспоненциальные позиции, т. е. в степени 2.

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

Излишне говорить, что коллекция должна быть отсортирована, чтобы это сработало.

Реализация

public static int exponentialSearch(int[] integers, int elementToSearch) {

    if (integers[0] == elementToSearch)
        return 0;
    if (integers[integers.length - 1] == elementToSearch)
        return integers.length;

    int range = 1;

    while (range < integers.length && integers[range] <= elementToSearch) {
        range = range * 2;
    }

    return Arrays.binarySearch(integers, range / 2, Math.min(range, integers.length), elementToSearch);
}

Мы можем использовать этот алгоритм следующим образом:

int index = exponentialSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Вот как работает алгоритм:

Мы пытаемся найти элемент, который больше, чем элемент, который мы ищем. Мы делаем это, чтобы свести к минимуму диапазон элементов, которые мы ищем. Мы увеличиваем диапазон, умножая его на 2, и снова проверяем, достигли ли мы элемента, большего, чем элемент, который мы ищем, или конца массива. Как только что-либо из этого будет достигнуто, мы выйдем из цикла. Затем мы выполняем двоичный поиск с startIndex как диапазон/2 и lastIndex как диапазон .

В нашем случае это значение диапазона достигается при 8, а элемент в целых числах[8] равен 95. Итак, диапазон, в котором мы выполняем двоичный поиск, составляет:

startIndex = range/2 = 4

lastIndex = range = 8

При этом вызов двоичного поиска становится:

Arrays.binarySearch(integers, 4, 8, 6);

Выход:

67 found at Index 5

Здесь важно отметить, что мы можем ускорить умножение на 2, используя оператор сдвига влево диапазон << 1 вместо оператора * .

Временная Сложность

Наихудшая временная сложность для этого типа поиска составляет O(log(N)) .

Сложность Пространства

Этот алгоритм требует O(1) пространства для хранения искомого элемента, если базовый алгоритм двоичного поиска является итерационным.

Если базовый алгоритм двоичного поиска рекурсивен, сложность пространства становится O(log(N)) .

Приложения

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

Поиск Фибоначчи

Объяснение

Поиск Фибоначчи использует подход “разделяй и властвуй”, при котором мы неравномерно разделяем элемент в соответствии с рядом Фибоначчи. Этот поиск требует сортировки массива.

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

Помните, что формула для рядов Фибоначчи такова:

$$ (N-1)+Фибо(N-2) $$

Первые два числа в этой серии – Фибо(0) и Фибо(1) . Итак, согласно этой формуле, серия выглядит следующим образом 0, 1, 1, 2, 3, 5, 8, 13, 21… Интересные наблюдения, которые следует отметить здесь, заключаются в том, что:

Фибо(N-2) составляет приблизительно 1/3 от Фибо(N)

Фибо(N-1) составляет примерно 2/3 от Фибо(N)

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

Реализация

Давайте взглянем на реализацию, чтобы получить более четкое представление:

public static int fibonacciSearch(int[] integers, int elementToSearch) {

    int fibonacciMinus2 = 0;
    int fibonacciMinus1 = 1;
    int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
    int arrayLength = integers.length;

    while (fibonacciNumber < arrayLength) {
        fibonacciMinus2 = fibonacciMinus1;
        fibonacciMinus1 = fibonacciNumber;
        fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
    }

    int offset = -1;

    while (fibonacciNumber > 1) {
        int i = Math.min(offset+fibonacciMinus2, arrayLength-1);

        if (integers[i] < elementToSearch) {
            fibonacciNumber = fibonacciMinus1;
            fibonacciMinus1 = fibonacciMinus2;
            fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
            offset = i;
        }

        else if (integers[i] > elementToSearch) {
            fibonacciNumber = fibonacciMinus2;
            fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2;
            fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
        }

        else return i;
    }

    if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch)
        return offset+1;

    return -1;
}

Мы можем запустить этот алгоритм следующим образом:

int index = fibonacciSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Вот как работает алгоритм:

Он начинается с первого нахождения числа в ряду Фибоначчи, ближайшего к массиву, но большего, чем длина массива. Это происходит, когда Число Фибоначчи равно 13, что просто больше длины массива – 10.

Затем мы сравниваем элементы массива и на основе этого сравнения выполняем одно из следующих действий:

• Сравните элемент для поиска с элементом в fibonacciMinus2 и верните индекс, если значение совпадает.
• Если elementToSearch больше текущего элемента, мы перемещаемся на один шаг назад в ряду Фибоначчи и меняем значения fibonacciNumber , fibonacciMinus1 & fibonacciMinus2 соответственно. Смещение сбрасывается до текущего индекса.
• Если elementToSearch меньше текущего элемента, мы перемещаемся на два шага назад в ряду Фибоначчи и меняем значения fibonacciNumber , fibonacciMinus1 & fibonacciMinus2 соответственно.

Выход:

67 found at Index 5

Временная Сложность

Наихудшая временная сложность для этого поиска- O(log(N)) .

Сложность Пространства

В то время как нам нужно сохранить три числа в ряду Фибоначчи и элемент для поиска, нам нужно четыре дополнительных единицы пространства.

Это требование к пространству не увеличивается с увеличением размера входного массива. Следовательно, мы можем сказать, что сложность пространства для поиска Фибоначчи равна O(1) .

Приложения

Этот поиск используется, когда разделение является дорогостоящей операцией для центрального процессора. Такие алгоритмы, как двоичный поиск, как правило, работают плохо, поскольку они используют деление для разделения массива.

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

API коллекций Java

Теперь, когда мы увидели реализацию нескольких алгоритмов в Java, давайте также кратко рассмотрим, как выполняется поиск в различных коллекциях Java.

Массивы

Массивы в Java можно искать с помощью одного из java.util.Бинарный поиск методы. Двоичный поиск в версии OpenJDK использует итеративную форму поиска.

Давайте быстро рассмотрим, как мы можем использовать этот метод:

int[] integers = {3, 22, 27, 47, 57, 67, 89, 91, 95, 99};

int elementToSearch = 67;

int index = java.util.Arrays.binarySearch(integers, elementToSearch);

Выход:

67 found at Index 5

Интерфейс Списка

Интерфейс списка имеет в основном два метода, которые можно использовать для поиска: indexOf() и содержит() .

Метод indexOf() возвращает индекс элемента, если он существует в списке или -1 если его не существует.

Метод contains() возвращает true или false в зависимости от наличия элемента. Он внутренне вызывает индекс метода () .

Интерфейс List использует последовательный поиск для выполнения поиска по индексу, и, следовательно, его временная сложность составляет O(N) .

Давайте попробуем выполнить поисковую операцию в Списке :

java.util.List integers = new java.util.ArrayList<>();
integers.add(3);
integers.add(22);
integers.add(27);
integers.add(47);
integers.add(57);
integers.add(67);
integers.add(89);
integers.add(91);
integers.add(95);
integers.add(99);

int elementToSearch = 67;

int index = integers.indexOf(elementToSearch);

Выход:

67 found at Index 5

Аналогично, если мы не заинтересованы в индексе, а только хотим знать, существует ли элемент в списке или нет, мы можем использовать метод contains() :

integers.contains(67)

Выход:

true

Интерфейс Карты

Карта представляет собой структуру данных пары ключ-значение. Интерфейс Map в Java использует Поиск на основе хэша , а также Двоичное дерево поиска .

Файл java.util.Класс HashMap использует хэш-значение ключа для хранения элементов на карте. Извлечение элемента с карты с использованием правильных ключей для хэширования и хорошего алгоритма хэширования (такого, чтобы не возникало столкновений) – это O(1) .

Другой реализацией интерфейса карты является java.util.Древовидная карта , которая внутренне использует Красно-черное дерево , представляющее собой тип самобалансирующегося двоичного дерева поиска. Элементы, добавленные в это дерево, автоматически сохраняются в отсортированном виде по дереву.

Временная сложность поиска двоичного дерева составляет O(log(N)) .

Давайте посмотрим, как мы можем искать элемент на карте:

java.util.Map integers = new java.util.HashMap<>();
integers.put(3,"three");
integers.put(22,"twentytwo");
integers.put(27,"twentyseven");
integers.put(47,"fortyseven");
integers.put(57,"fiftyseven");
integers.put(67,"sixtyseven");
integers.put(89,"eightynine");
integers.put(91,"ninetyone");
integers.put(95,"ninetyfive");
integers.put(99,"ninetynine");

String value = integers.get(67);

System.out.println("the value at key 67 is: " + value);

Мы создали карту с ключом в виде целого числа и значением в виде этого целого числа в словах. Затем мы ищем ключ и получаем целое число в виде слов в выходных данных.

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

Выход:

the value at key 67 is: sixtyseven

Интерфейс Map также содержит метод containsKey () , который можно использовать для определения того, существует ли данный ключ или нет:

integers.containsKey(67);

Установленный Интерфейс

Структура данных Set используется для хранения уникальных элементов. Интерфейс Set по сути является оболочкой над интерфейсом Map , описанным выше, для хранения элементов в ключе Map .

Как и в интерфейсе Map , он использует Двоичный и Поиск на основе хэша .

java.util.Set integers = new java.util.HashSet<>();
integers.add(3);
integers.add(22);
integers.add(27);
integers.add(47);
integers.add(57);
integers.add(67);
integers.add(89);
integers.add(91);
integers.add(95);
integers.add(99);

int elementToSearch = 67;

boolean isNumberExists = integers.contains(elementToSearch);

if (isNumberExists)
    System.out.println(elementToSearch + " exists in the set");
else
    System.out.println(elementToSearch + " does not exist in the set");

В интерфейсе Set нет индекса, и поэтому операция поиска содержит() возвращает true или false в зависимости от наличия элемента, в котором выполняется поиск.

В этом случае, поскольку элемент существует в наборе, мы получаем следующий вывод:

67 exists in the set

Сравнение Времени Алгоритма Поиска

Тем не менее, часто бывает полезно запустить все эти алгоритмы несколько раз, чтобы получить представление о том, как они работают.

Давайте поищем элемент 573400 в отсортированном массиве, заполненном миллионом целых чисел.

Вот результаты алгоритмов:

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

Также легко увидеть, что двоичный поиск, интерполяция и поиск по Фибоначчи показывают наилучшие результаты для этого конкретного массива.

Вывод

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

В этой статье мы рассмотрели, как работают различные алгоритмы поиска и при каких обстоятельствах они идеально подходят. Мы также рассмотрели, как Java использует различные алгоритмы поиска в своем встроенном API коллекций.

Как всегда, вы можете найти исходный код алгоритмов, описанных в этой статье здесь .