/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/searches/ExponentalSearch.java
51 строка
2 KB
Hardik Pawar
Add tests, remove `main`, improve docs in `ExponentialSearch` (#5664)
10 окт 2024, 22:30
Не верифицирован
10 окт 2024, 22:30
d197fc7
Код
Авторство
О чём код?
package com.thealgorithms.searches; import com.thealgorithms.devutils.searches.SearchAlgorithm; import java.util.Arrays; /** * ExponentialSearch is an algorithm that efficiently finds the position of a target * value within a sorted array. It works by expanding the range to find the bounds * where the target might exist and then using binary search within that range. * * <p> * Worst-case time complexity: O(log n) * Best-case time complexity: O(1) when the element is found at the first position. * Average time complexity: O(log n) * Worst-case space complexity: O(1) * </p> * * <p> * Note: This algorithm requires that the input array be sorted. * </p> */ class ExponentialSearch implements SearchAlgorithm { /** * Finds the index of the specified key in a sorted array using exponential search. * * @param array The sorted array to search. * @param key The element to search for. * @param <T> The type of the elements in the array, which must be comparable. * @return The index of the key if found, otherwise -1. */ @Override public <T extends Comparable<T>> int find(T[] array, T key) { if (array.length == 0) { return -1; } if (array[0].equals(key)) { return 0; } if (array[array.length - 1].equals(key)) { return array.length - 1; } int range = 1; while (range < array.length && array[range].compareTo(key) < 0) { range = range * 2; } return Arrays.binarySearch(array, range / 2, Math.min(range, array.length), key); } }