Recherche par saut :
Comme Binary Search , Jump Search est un algorithme de recherche de tableaux triés. L'idée de base est de vérifier moins d'éléments (que la recherche linéaire ) en avançant par étapes fixes ou en sautant certains éléments au lieu de rechercher tous les éléments.
Par exemple, supposons que nous ayons un tableau arr[] de taille n et un bloc (à sauter) de taille m. Ensuite, nous cherchons dans les index arr[0], arr[m], arr[2m]…..arr[km] et ainsi de suite. Une fois que nous avons trouvé l'intervalle (arr[km] < x < arr[(k+1)m]), nous effectuons une opération de recherche linéaire à partir de l'indice km pour trouver l'élément x.
Considérons le tableau suivant : (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). La longueur du tableau est de 16. La recherche de saut trouvera la valeur de 55 avec les étapes suivantes en supposant que la taille de bloc à sauter est de 4.
ÉTAPE 1 : Sauter de l'index 0 à l'index 4 ;
ÉTAPE 2 : Passer de l'index 4 à l'index 8 ;
ÉTAPE 3 : Passer de l'index 8 à l'index 12 ;
ÉTAPE 4 : Puisque l'élément à l'index 12 est supérieur à 55, nous allons revenir en arrière pour arriver à l'index 8.
ÉTAPE 5 : Effectuez une recherche linéaire à partir de l'index 8 pour obtenir l'élément 55.
Performances par rapport à la recherche linéaire et binaire :
Si nous le comparons avec la recherche linéaire et binaire, il en ressort qu'il est meilleur que la recherche linéaire mais pas meilleur que la recherche binaire.
Quelle est la taille de bloc optimale à ignorer ?
Dans le pire des cas, on doit faire n/m sauts, et si la dernière valeur cochée est supérieure à l'élément à rechercher, on effectue m-1 comparaisons en plus pour la recherche linéaire. Par conséquent, le nombre total de comparaisons dans le pire des cas sera ((n/m) + m-1). La valeur de la fonction ((n/m) + m-1) sera minimale lorsque m = √n. Par conséquent, la meilleure taille de pas est m = √n.
int min(int a, int b){
if(b>a)
return a;
else
return b;
}
int jumpsearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt
;
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] < x)
{
prev = step;
step += sqrt;
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
int main()
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
int x = 55;
int n = sizeof(arr)/sizeof(arr[0]);
int index = jumpsearch(arr, x, n);
if(index >= 0)
printf("Number is at %d index",index);
else
printf("Number is not exist in the array");
return 0;
}