Упражнения на Java: поиск указанного элемента в указанном отсортированном массиве элементов с помощью Jump Search

Поиск Java: Упражнение-3 с решением

Напишите Java-программу для поиска указанного элемента в заданном отсортированном массиве элементов с помощью Jump Search.

В Википедии, в информатике, поиск с перескоком или поиск блоков относится к алгоритму поиска упорядоченных списков. Он работает, сначала проверяя все элементы L _km , где ℜ ∈ ℵ и m - размер блока, пока не будет найден элемент, который больше, чем ключ поиска. Чтобы найти точное положение поискового ключа в списке, по подсписку L _{[(k-1) m, km]} выполняется линейный поиск.
Алгоритм:
Вход: упорядоченный список L, его длина n и поисковый ключ s.
Вывод: позиция s в L или ничего, если s не в L.

 ← 0
  б ← [√n]
  в то время как Lmin (b, n) -1 <s делают
    а б
    b ← b + [√n]
    если ≥ n, то
      ничего не вернуть
  в то время как La делает
    а ← а + 1
    если a = min (b, n)
      ничего не вернуть
  если La = s, то
    вернуть
  еще
    ничего не вернуть

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

Java-код:

public class Main {
	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 = jumpSearch(nums, search_num);
       System.out.println(search_num + " is found at index " + index_result);
	}
	
	    public static int jumpSearch(int[] nums, int item)	    {
	        
	    	int array_size = nums.length;
	 
	        // Find block size to be jumped
	        int block_size = (int)Math.floor(Math.sqrt(array_size));
	 
	        // If the element is present find the block where element is present
	        int prev_item = 0;
	        while (nums[Math.min(block_size, array_size)-1] < item)
	        {
	            prev_item = block_size;
	            block_size += (int)Math.floor(Math.sqrt(array_size));
	            if (prev_item >= array_size)
	                return -1;
	        }
	 
	        // Using a linear search for element in block beginning with previous item
	        while (nums[prev_item] < item)
	        {
	            prev_item++;
	            if (prev_item == Math.min(block_size, array_size))
	                return -1;
	        }
	 
	        // If element is found
	        if (nums[prev_item] == item)
	            return prev_item;
	 
	        return -1;
	    } 	    
}

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

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

Блок - схема:

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

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

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