Мастерство в двоичном поиске на Java

Введение

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

Создайте отсортированный массив

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

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

Реализовать двоичный поиск итеративно

Теперь мы реализуем алгоритм двоичного поиска итеративно. Этот метод возвращает индекс элемента, если он присутствует в массиве. В противном случае возвращает -1.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

Для запуска кода сначала нужно вызвать метод binarySearchIterative, передав sortedArray и элемент, который мы хотим найти, в качестве параметров.

## скомпилировать java-файл
javac BinarySearch.java

## запустить файл
java BinarySearch

Реализовать двоичный поиск рекурсивно

Теперь мы реализуем алгоритм двоичного поиска рекурсивно. Этот метод также возвращает индекс элемента, если он присутствует в массиве. В противном случае возвращает -1.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

Для запуска кода нужно вызвать метод binarySearchRecursive, передав sortedArray, элемент, который мы хотим найти, leftIdx и rightIdx в качестве параметров.

Использовать встроенные методы для двоичного поиска

В Java также есть встроенные функции для реализации двоичного поиска. Эти функции - Arrays.binarySearch() и Collections.binarySearch(). Мы можем использовать эти функции для поиска элемента в отсортированном массиве.

Функция Arrays.binarySearch() принимает в качестве параметров отсортированный массив и значение ключа для поиска. Функция возвращает индекс ключа, если он присутствует в массиве. В противном случае возвращает -1.

int index = Arrays.binarySearch(sortedArray, 6);

Функция Collections.binarySearch() может быть использована для коллекций, таких как ArrayLists, для поиска элемента. Функция принимает в качестве параметров отсортированную коллекцию и ключ и возвращает индекс, по которому находится ключ. В противном случае возвращает -1.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

Тест

Теперь мы протестируем все методы и выведем результат.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

Для запуска кода сначала компилируем java - программу.

javac BinarySearch.java

Затем мы можем запустить программу.

java BinarySearch

Резюме

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

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