Recherche de saut

La recherche de saut est un algorithme de recherche par intervalle. C’est un algorithme relativement nouveau qui ne fonctionne que sur des tableaux triés. Il tente de réduire le nombre de comparaisons nécessaires par rapport à la recherche linéaire en ne balayant pas chaque élément comme la recherche linéaire. Dans la recherche par saut, le tableau est divisé en blocs m. Il recherche l’élément dans un bloc et, si l’élément n’est pas présent, il passe au bloc suivant. Lorsque l’algorithme trouve le bloc contenant l’élément, il utilise l’algorithme de recherche linéaire pour trouver l’index exact. Cet algorithme est plus rapide que la recherche linéaire, mais plus lent que la recherche dichotomique.

Algorithme de recherche par saut

Supposons que nous ayons un tableau non trié A[] contenant n éléments, et que nous voulons trouver un élément X.

Exemple de recherche par saut

Supposons que nous ayons le tableau : (1, 2, 3, 4, 5, 6, 7, 8, 9), et que nous voulions trouver X - 7.

Puisqu’il y a 9 éléments, nous avons n comme 9.

Mise en œuvre de l’algorithme de recherche par saut

#include <bits/stdc++.h>
using namespace std;

int jumpSearch(int arr[], int x, int n) {
  int m = sqrt(n);
  int i = 0;
  while (arr[min(m, n) - 1] < x) {
    i = m;
    m += sqrt(n);
    if (i >= n) return -1;
  }
  while (arr[i] < x) {
    i++;
    if (i == min(m, n)) return -1;
  }
  if (arr[i] == x) return i;

  return -1;
}

int main() {
  int n = 10;
  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 7;
  int result = jumpSearch(arr, x, n);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index " << result;
}

Complexité de l’algorithme de recherche par saut

Complexité du temps

• Cas moyen

L’algorithme de tri par saut s’exécute n / m fois où n est le nombre d’éléments et m est la taille du bloc. La recherche linéaire nécessite des comparaisons m-1 faisant l’expression de temps total n / m + m-1. La valeur la plus optimale de m minimisant l’expression temporelle est √n, ce qui rend la complexité temporelle n / √n + √n, c’est-à-dire √n. La complexité temporelle de l’algorithme de recherche par sauts est O(√n).

• Meilleur cas

Le meilleur cas de complexité temporelle est O(1). Elle se produit lorsque l’élément à rechercher est le premier élément présent dans le tableau.

• Pire cas

Le pire cas se produit lorsque nous effectuons des sauts n/m, et que la dernière valeur que nous avons vérifiée est supérieure à l’élément que nous recherchons, et les comparaisons m-1 sont effectuées pour une recherche linéaire. Le pire cas de complexité temporelle est celui de O(√n).

Complexité spatiale

La complexité spatiale de cet algorithme est O(1) car il ne nécessite aucune structure de données autre que des variables temporaires.