Бинарный поиск в Java

Бинарный поиск - это алгоритм поиска элемента в отсортированном массиве или списке, который выполняется путем постоянного деления пространства поиска пополам. Это эффективный алгоритм поиска, который имеет логарифмическую сложность времени выполнения O(log n), где n - размер массива или списка.

Вот пример реализации бинарного поиска на Java:

java
public class BinarySearch {
    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == key) {
                return mid;
            }
            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int key = 23;
        int result = binarySearch(arr, key);
        if (result == -1) {
            System.out.println("Элемент не найден");
        } else {
            System.out.println("Элемент найден в индексе " + result);
        }
    }
}

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

В результате выполнения программы будет выведено:

"Элемент найден в индексе 5", т.к. элемент с ключом 23 находится в позиции 5 в массиве arr.

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