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

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

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

Из Википедии Интерполяционный поиск - это алгоритм поиска ключа в массиве, который был упорядочен по числовым значениям, назначенным ключам (значениям ключей). Впервые он был описан В. В. Петерсоном в 1957 году. Интерполяционный поиск напоминает метод, с помощью которого люди ищут в телефонном справочнике имя (ключевое значение, по которому упорядочиваются записи в книге): на каждом этапе алгоритм вычисляет, где в оставшемся пространстве поиска искомый элемент может быть основан на значениях ключа в границах пространства поиска и значении искомого ключа, обычно с помощью линейной интерполяции. Значение ключа, фактически найденное в этой предполагаемой позиции, затем сравнивается с искомым значением ключа. Если он не равен, то в зависимости от сравнения оставшееся пространство поиска уменьшается до части до или после расчетной позиции. Этот метод будет работать только в том случае, если расчеты размера различий между ключевыми значениями являются разумными.

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

Java-код:

public class Main {
    public static void main(String[] args){
        int nums[] = {1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 21, 34, 45, 91, 120, 130, 456, 564};
        int searched_num = 91;
	   // Find the index of searched item
        int index_result = Interpolation_search(nums, searched_num);
        System.out.println(searched_num + " is found at index " + index_result);
    }
    public static int Interpolation_search(int[] nums, int searched_num) {
        int low_num = 0;
        int high_num = nums.length - 1;
        int mid_num;
        while (nums[high_num] != nums[low_num] && nums[low_num] < searched_num && nums[high_num] >= searched_num) {
            mid_num = low_num + ((searched_num - nums[low_num]) * (high_num - low_num) / (nums[high_num] - nums[low_num]));
            if (searched_num > nums[mid_num])
                low_num = mid_num + 1;
            else if (searched_num < nums[mid_num])
                high_num = mid_num - 1;
            else
                return mid_num;
        }
        if (nums[low_num] == searched_num) {
            return low_num;
        } else {
            return -1;
        }
    }
}

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

 91 находится по индексу 13

Блок - схема:

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

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

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