Ola pessoal, estou trabalhando com um algoritmo de busca chamado de JumpSearch, aparentemente ele esta correto, mas por algum motivo ele me retorna o valor do contador errado, e eu gostaria de saber o prq ? Voces podem me ajudar ?
Estou testando este método com a chave 2, entao eu quero encontrar o número 2 em um arranjo ordenado, porém o contador está me retornando 3 interações, porque ? Como eu consigo corrigir ?
Note que a raiz de 9 é 3, então o meu salto é de 3 em 3, e como meu arranjo { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } o contador não deveria ser 1 ? Pois, no primeiro salto eu já encontraria 2 !
public class JumpSearch {
public static void main(String[] args) {
int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int search_item = 2;
// Find the index of 'search_item' using Jump Search
int location = jump_search(array, search_item);
// Print the index where search_item is located
System.out.println(search_item + " is found at index " + location);
}
public static int jump_search(int[] arr, int item) {
int array_size = arr.length;
int block_size = (int)Math.floor(Math.sqrt(array_size));
int iterations = 0; // Variável de contagem de iterações
int prev = 0;
while (arr[Math.min(block_size, array_size)-1] < item) {
prev = block_size;
block_size += (int)Math.floor(Math.sqrt(array_size));
iterations++; // Incrementa o contador de iterações
if (prev >= array_size)
return -1;
}
while (arr[prev] < item) {
prev++;
iterations++; // Incrementa o contador de iterações
if (prev == Math.min(block_size, array_size))
return -1;
}
if (arr[prev] == item) {
iterations++; // Incrementa o contador de iterações
System.out.println("Número de iterações: " + iterations);
return prev;
}
return -1;
}
}