Algorithme - Sauter la recherche

Par exemple, supposons que nous ayons un tableau arr[] de taille n et un bloc (à sauter) de taille m. Ensuite on recherche les indices arr[0], arr[m], arr[2m]... ..arr[km] et ainsi de suite. Une fois qu'on a trouvé l'intervalle (arr [km]

On considère 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. Une recherche par saut en trouvera 55 dans les étapes suivantes, en supposant que la taille du bloc à ignorer est de 4.

Étape 1 : Sauter de l'index 0 à l'index 4 ;
Étape 2 : Sauter de l'index 4 à l'index 8 ;
Étape 3 : Sauter de l'index 8 à l'index 16 ;
Étape 4 : Puisque l'élément à l'index 16 est supérieur à 55, nous remonterons d'un pas jusqu'à l'index 9.
Étape 5 : Effectuez une recherche linéaire à partir de l'index 9 pour obtenir l'élément 55.
Quelle est la taille optimale des morceaux à sauter ?
Dans le pire des cas, nous devons faire n/m sauts et faire m-1 comparaisons avec une recherche linéaire si la dernière valeur vérifiée est supérieure à l'élément recherché. Par conséquent, le nombre total de comparaisons dans le pire des cas sera ((n/m) + m-1). Lorsque m =√n, la valeur de la fonction ((n/m) + m-1) sera la valeur minimale. Par conséquent, la meilleure taille de pas est m = √n.

// C++ program to implement Jump Search

#include <bits>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>Sortie : </p>
<p>Le numéro 55 est à l'index 10</p>
<p>Complexité temporelle : O(√n)<br>
Espace auxiliaire : O(1)</p>
<p><strong>Attention :</strong></p>
<p>Cette recherche ne fonctionne que sur les tableaux triés. <br>
La taille optimale des morceaux à ignorer est O(√n). Cela rend la recherche par saut O(√n) complexe en temps. <br>
La complexité temporelle de la recherche par saut se situe entre la recherche linéaire ((O(n))) et la recherche binaire (O(Log n)).
La recherche binaire est meilleure que la recherche par saut, mais la recherche par saut a l'avantage de ne parcourir qu'une seule fois (la recherche binaire peut nécessiter au plus 0 (Log n) sauts, étant donné que l'élément recherché est le plus petit élément ou moins que le plus petit). Par conséquent, dans les systèmes où revenir en arrière coûte cher, nous utilisons Jump Search. <br></p></bits>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!