Recherche dichotomique

1. Algorithme de Recherche dichotomique
2. Exemple de Recherche dichotomique
3. Mise en œuvre de l’algorithme de Recherche dichotomique
4. Complexité de l’algorithme de Recherche dichotomique

La Recherche dichotomique est l’algorithme de recherche le plus populaire et le plus efficace. En fait, c’est l’algorithme de recherche le plus rapide. Tout comme le tri par saut, elle a également besoin de trier le tableau. Il est basé sur l’approche diviser pour mieux régner, qui consiste à diviser le tableau en deux moitiés et à comparer l’élément que nous recherchons avec l’élément du milieu. Si l’élément du milieu correspond, nous renvoyons l’index de l’élément du milieu ; sinon, nous nous déplaçons vers la moitié gauche et la moitié droite en fonction de la valeur de l’élément.

Algorithme de Recherche dichotomique

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

Exemple de Recherche dichotomique

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

Mise en œuvre de l’algorithme de Recherche dichotomique

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

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

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

Complexité de l’algorithme de Recherche dichotomique

Complexité du temps

• Cas moyen

Lorsque nous effectuons une Recherche dichotomique, nous cherchons dans une moitié et nous rejetons l’autre moitié, réduisant chaque fois la taille du tableau de moitié.

L’expression de la complexité temporelle est donnée par la récurrence.

T(n) = T(n/2) + k , k is a constant.

Le résultat de cette récurrence donne logn, et la complexité temporelle est de l’ordre de O(logn). Elle est plus rapide que la recherche linéaire et la recherche par saut.

• Meilleur cas

Le meilleur cas se produit lorsque l’élément du milieu est celui que nous recherchons et qu’il est renvoyé à la première itération. La complexité temporelle dans le meilleur des cas est O(1).

• Pire cas

La complexité temporelle du pire cas est la même que la complexité temporelle moyenne. Le pire cas de complexité temporelle est le O(logn).

Complexité spatiale

La complexité spatiale de cet algorithme est O(1) dans le cas d’une implémentation itérative car il ne nécessite aucune structure de données autre que des variables temporaires.

Dans le cas d’une implémentation récursive, la complexité spatiale est de O(logn) en raison de l’espace requis par la pile d’appels récursifs.