Реализация бинарного поиска в отсортированном массиве

Условие

Дается отсортированный массив целых чисел и целевое значение. Требуется: 1)Реализовать бинарный поиск (алгоритм, который делит массив пополам и рекурсивно ищет элемент). 2)Вернуть индекс элемента, если он найден, или -1, если отсутствует.

public class Main{

    public static void main(String[] args) {
        int arr[] = {1, 3, 5, 6, 8, 12};
    }
}

Ответ

В рекурсивном бинарном поиске средний элемент делит текущий диапазон пополам. Если target меньше него, ищите слева, иначе справа; при пустом диапазоне верните −1.

static int search(int[] a, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (a[mid] == target) return mid;
    return target < a[mid]
            ? search(a, target, left, mid - 1)
            : search(a, target, mid + 1, right);
}

Вызов: search(arr, target, 0, arr.length - 1). Для target=8 в примере результат 4. Время O(log n), стек O(log n). Массив должен быть отсортирован по возрастанию; при дубликатах возвращается любое найденное вхождение.