Recherche dichotomique

Harshit Jindal 12 octobre 2023
  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
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.

  • Mettez lo comme 0 et hi comme n - 1.
  • Pendant que lo < hi:
    • Réglez mid = lo + (hi - lo) / 2.
    • si A[mid] == X renvoie mid.
    • si A[mid] <X alors lo = mid + 1.
    • sinon si A[mid]> X alors hi = mid-1.
  • L’élément n’est pas trouvé, donc retournez -1.

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.

  • Définissez lo sur 0 et hi sur 8.
  • Calculez mid comme 4. Puisque A[mid] <X, définissez lo = 4 + 1 = 5.
  • Calculez mid comme 6. Puisque A[mid] <X, définissez lo = 6 + 1 = 7.
  • Calculez le milieu comme 7. Puisque A[mid] == 8, renvoie 7.

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.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Article connexe - Search Algorithm