Поиск элемента в отсортированном массиве с помощью рекурсии

Условие

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

public class Live {
    public static void main(String[] args) {
        // пример использования
    }

    public static int searchRecursive(int[] nums, int target, int left, int right) {
        // реализация
    }
}

Ответ

Примените бинарный поиск: сравните target со средним элементом и рекурсивно продолжите только в одной половине диапазона. Пустой диапазон означает отсутствие значения.

public static int searchRecursive(int[] nums, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target)
        return searchRecursive(nums, target, mid + 1, right);
    return searchRecursive(nums, target, left, mid - 1);
}

Начальный вызов: searchRecursive(nums, target, 0, nums.length - 1). Требуется возрастающая сортировка и ненулевой массив; при дубликатах возвращается любой найденный индекс. Время O(log n), стек O(log n). Итеративный вариант уменьшил бы дополнительную память до O(1).