Упражнения на Java: поиск указанного элемента в заданном отсортированном массиве элементов с использованием экспоненциального поиска

Поиск Java: упражнение 5 с решением

Напишите программу на Java, чтобы найти указанный элемент в заданном отсортированном массиве элементов, используя экспоненциальный поиск.

Из Википедии, в информатике, экспоненциальный поиск (также называемый двойным или скачущим поиском или поиском Струзика) - это алгоритм, созданный Джоном Бентли и Эндрю Чи-Чи Яо в 1976 году для поиска отсортированных, неограниченных / бесконечных списков. Существует множество способов реализовать это, наиболее распространенным из которых является определение диапазона, в котором находится ключ поиска, и выполнение двоичного поиска в этом диапазоне. Для этого требуется O (log i), где i - это позиция ключа поиска в списке, если ключ поиска находится в списке, или позиция, где должен быть ключ поиска, если ключ поиска отсутствует в списке.

Пример решения:

Java-код:

import java.util.Arrays;
public class abc {
	public static void main(String[] args) {
		int nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 21, 34, 45, 91, 120, 130, 456, 564};
        int search_num = 120;
		
		// Find the index of searched item
       int index_result = exponentialSearch(nums, search_num);
       System.out.println(search_num + " is found at index " + index_result);		
		
	}
	private static int exponentialSearch(int[] arr, int i) {
		int start_num = 0;
		
		if(arr[start_num] == i)
			return start_num;
		start_num =1;
		while(start_num < arr.length && arr[start_num] <= i) {
			start_num*=2;
		}
		return Arrays.binarySearch(arr, start_num/2, Math.min(start_num, arr.length), i);
	}
}

Пример вывода:

 120 находится по индексу 12

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на Java, чтобы найти указанный элемент в данном массиве элементов, используя поиск интерполяции.
Далее: Напишите программу на Java, чтобы найти указанный элемент в данном массиве элементов, используя тернарный поиск.