logo

TechCodeview

Algorithme de recherche binaire – Implémentation itérative et récursive

Recherche binaire Algorithme est un algorithme de recherche utilisé dans un tableau trié par diviser à plusieurs reprises l'intervalle de recherche en deux . L'idée de la recherche binaire est d'utiliser les informations selon lesquelles le tableau est trié et de réduire la complexité temporelle à O (log N).

Recherche binaire est un algorithme de recherche utilisé pour trouver la position d'une valeur cible dans un trié tableau. Il fonctionne en divisant à plusieurs reprises l'intervalle de recherche en deux jusqu'à ce que la valeur cible soit trouvée ou que l'intervalle soit vide. L'intervalle de recherche est réduit de moitié en comparant l'élément cible avec la valeur médiane de l'espace de recherche.

Shehzad Poonawala

Pour appliquer l'algorithme de recherche binaire :



  • La structure des données doit être triée.
  • L'accès à n'importe quel élément de la structure de données prend un temps constant.

Algorithme de recherche binaire :

Dans cet algorithme,

  • Divisez l'espace de recherche en deux moitiés en trouver l'index du milieu .

Trouver l'index du milieu dans l'algorithme de recherche binaire

  • Comparez l'élément central de l'espace de recherche avec la clé.
  • Si la clé est trouvée au niveau de l'élément central, le processus est terminé.
  • Si la clé n'est pas trouvée au niveau de l'élément du milieu, choisissez quelle moitié sera utilisée comme prochain espace de recherche.
    • Si la clé est plus petite que l’élément du milieu, alors le côté gauche est utilisé pour la prochaine recherche.
    • Si la clé est plus grande que l'élément du milieu, alors le côté droit est utilisé pour la prochaine recherche.
  • Ce processus se poursuit jusqu'à ce que la clé soit trouvée ou que l'espace de recherche total soit épuisé.

Comment fonctionne l’algorithme de recherche binaire ?

Pour comprendre le fonctionnement de la recherche binaire, considérons l'illustration suivante :

Considérons un tableau arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , et le cible = 23 .

Premier pas: Calculez le milieu et comparez l'élément médian avec la clé. Si la clé est inférieure à l'élément médian, déplacez-vous vers la gauche et si elle est supérieure au milieu, déplacez l'espace de recherche vers la droite.

  • La clé (c'est-à-dire 23) est supérieure à l'élément médian actuel (c'est-à-dire 16). L'espace de recherche se déplace vers la droite.

Algorithme de recherche binaire : comparer la clé avec 16

  • La clé est inférieure au milieu actuel de 56. L'espace de recherche se déplace vers la gauche.

Algorithme de recherche binaire : comparer la clé avec 56

Deuxième étape: Si la clé correspond à la valeur de l'élément médian, l'élément est trouvé et arrête la recherche.

Algorithme de recherche binaire : correspondances clés avec le milieu

Pratique recommandée Recherche binaire Essayez-le !

Le Algorithme de recherche binaire peut être mis en œuvre des deux manières suivantes

  • Algorithme de recherche binaire itératif
  • Algorithme de recherche binaire récursif

Vous trouverez ci-dessous les pseudocodes des approches.

Algorithme de recherche binaire itérative :

Ici, nous utilisons une boucle while pour continuer le processus de comparaison de la clé et de division de l'espace de recherche en deux moitiés.

Implémentation d'un algorithme de recherche binaire itérative :

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Java 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Python 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
Javascript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= faible) { moyen = faible + Math.floor((haut - bas) / 2);    // Si l'élément est présent au milieu // lui-même if (arr[mid] == x) return mid;    // Si l'élément est plus petit que mid, alors // il ne peut être présent dans le sous-tableau gauche que si (arr[mid]> x) high = mid - 1;    // Sinon, l'élément ne peut être présent // que dans le sous-tableau droit, sinon low = mid + 1;  } // Nous arrivons ici lorsque l'élément // n'est pas présent dans le tableau return -1; } arr =nouveau tableau(2, 3, 4, 10, 40);  x = 10 ;  n = longueur d'arrivée ;  résultat = binaireSearch(arr, x);   (résultat == -1) ? console.log('L'élément n'est pas présent dans le tableau') : console.log ('L'élément est présent à l'index ' + résultat);   // Ce code est contribué par simranarora5sos et rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Sortir 
Element is present at index 3>

Complexité temporelle : O (log N)
Espace auxiliaire : O(1)

Algorithme de recherche binaire récursif :

Créez une fonction récursive et comparez le milieu de l'espace de recherche avec la clé. Et en fonction du résultat, renvoyez l'index où se trouve la clé ou appelez la fonction récursive pour l'espace de recherche suivant.

Implémentation de l'algorithme de recherche binaire récursive :

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= bas) { int mid = bas + (haut - bas) / 2;  // Si l'élément est présent au milieu // lui-même if (arr[mid] == x) return mid;  // Si l'élément est plus petit que mid, alors // il ne peut être présent dans le sous-tableau gauche que si (arr[mid]> x) return binaireSearch(arr, low, mid - 1, x);  // Sinon, l'élément ne peut être présent que // dans le sous-tableau droit returnbinarySearch(arr, mid + 1, high, x);  } } // Code du pilote int main() { int arr[] = { 2, 3, 4, 10, 40 };  requête int = 10 ;  int n = taillede(arr) / taillede(arr[0]);  int résultat = binaireSearch(arr, 0, n - 1, requête);  (résultat == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= bas) { int mid = bas + (haut - bas) / 2;  // Si l'élément est présent au milieu // lui-même if (arr[mid] == x) return mid;  // Si l'élément est plus petit que mid, alors // il ne peut être présent dans le sous-tableau gauche que si (arr[mid]> x) return binaireSearch(arr, low, mid - 1, x);  // Sinon, l'élément ne peut être présent que // dans le sous-tableau droit returnbinarySearch(arr, mid + 1, high, x);  } // Nous arrivons ici lorsque l'élément // n'est pas présent dans le tableau return -1; } // Code du pilote int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = taillede(arr) / taillede(arr[0]);  entier x = 10 ;  int résultat = binaireSearch(arr, 0, n - 1, x);  (résultat == -1) ? printf('L'élément n'est pas présent dans le tableau') : printf('L'élément est présent à l'index %d', résultat);  renvoie 0 ; }>
Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= bas) { int mid = bas + (haut - bas) / 2;  // Si l'élément est présent au // milieu lui-même if (arr[mid] == x) return mid;  // Si l'élément est plus petit que mid, alors // il ne peut être présent dans le sous-tableau gauche que si (arr[mid]> x) return binaireSearch(arr, low, mid - 1, x);  // Sinon, l'élément ne peut être présent que // dans le sous-tableau droit returnbinarySearch(arr, mid + 1, high, x);  } // Nous arrivons ici lorsque l'élément n'est pas présent // dans le tableau return -1;  } // Code du pilote public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = {2, 3, 4, 10, 40 };  int n = arr.longueur ;  entier x = 10 ;  int résultat = ob.binarySearch(arr, 0, n - 1, x);  if (result == -1) System.out.println( 'L'élément n'est pas présent dans le tableau');  else System.out.println( 'L'élément est présent à l'index ' + résultat);  } } /* Ce code est contribué par Rajat Mishra */>
Python 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= low: mid = low + (high - low) // 2 # Si l'élément est présent au milieu lui-même if arr[mid] == x: return mid # Si l'élément est plus petit que mid, alors il # ne peut être présent dans le sous-tableau gauche elif arr[mid]> x : return binaireSearch(arr, low, mid-1, x) # Sinon, l'élément ne peut être présent que # dans le sous-tableau droit sinon : return binaireSearch(arr, mid + 1, high, x ) # L'élément n'est pas présent dans le tableau sinon : renvoie -1 # Code du pilote si __name__ == '__main__' : arr = [2, 3, 4, 10, 40] x = 10 # Résultat de l'appel de fonction = binaireSearch( arr, 0, len(arr)-1, x) if result != -1: print('L'élément est présent à l'index', résultat) else : print('L'élément n'est pas présent dans le tableau')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= bas) { int mid = bas + (haut - bas) / 2;  // Si l'élément est présent au // milieu lui-même if (arr[mid] == x) return mid;  // Si l'élément est plus petit que mid, alors // il ne peut être présent dans le sous-tableau gauche que si (arr[mid]> x) return binaireSearch(arr, low, mid - 1, x);  // Sinon, l'élément ne peut être présent que // dans le sous-tableau droit returnbinarySearch(arr, mid + 1, high, x);  } // Nous arrivons ici lorsque l'élément n'est pas présent // dans le tableau return -1;  } // Code du pilote public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Longueur ;  entier x = 10 ;  int résultat = binaireSearch(arr, 0, n - 1, x);  if (result == -1) Console.WriteLine( 'L'élément n'est pas présent dans l'arrau');  else Console.WriteLine('L'élément est présent à l'index ' + résultat);  } } // Ce code est fourni par Sam007.>
Javascript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= bas) { let mid = bas + Math.floor((haut - bas) / 2);  // Si l'élément est présent au milieu // lui-même if (arr[mid] == x) return mid;  // Si l'élément est plus petit que mid, alors // il ne peut être présent dans le sous-tableau gauche que si (arr[mid]> x) return binaireSearch(arr, low, mid - 1, x);  // Sinon, l'élément ne peut être présent que // dans le sous-tableau droit returnbinarySearch(arr, mid + 1, high, x);  } // Nous arrivons ici lorsque l'élément // n'est pas présent dans le tableau return -1; } soit arr = [ 2, 3, 4, 10, 40 ]; soit x = 10 ; let n = arr.length let result = binaireSearch(arr, 0, n - 1, x); (résultat == -1) ? console.log( 'L'élément n'est pas présent dans le tableau') : console.log('L'élément est présent à l'index ' +result);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $bas) { $mid = plafond($bas + ($haut - $bas) / 2); // Si l'élément est présent // au milieu lui-même if ($arr[$mid] == $x) return floor($mid); // Si l'élément est plus petit que // mid, alors il ne peut être // présent dans le sous-tableau gauche que si ($arr[$mid]> $x) renvoie binaireSearch($arr, $low, $mid - 1, $x ); // Sinon, l'élément ne peut // être présent que dans le sous-tableau droit returnbinarySearch($arr, $mid + 1, $high, $x); } // Nous arrivons ici lorsque l'élément // n'est pas présent dans le tableau return -1; } // Code du pilote $arr = array(2, 3, 4, 10, 40); $n = nombre($arr); $x = 10 ; $result = binaireSearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'L'élément n'est pas présent dans le tableau'; sinon echo 'L'élément est présent à l'index ', $result; ?>>
Sortir 
Element is present at index 3>
  • Complexité temporelle :
    • Meilleur cas : O(1)
    • Cas moyen : O (log N)
    • Pire des cas : O (log N)
  • Espace auxiliaire : O(1), si la pile d'appels récursifs est considérée alors l'espace auxiliaire sera O(logN).
  • La recherche binaire peut être utilisée comme élément de base pour des algorithmes plus complexes utilisés dans l'apprentissage automatique, tels que des algorithmes pour entraîner des réseaux neuronaux ou trouver les hyperparamètres optimaux pour un modèle.
  • Il peut être utilisé pour la recherche en infographie telle que des algorithmes de lancer de rayons ou de mappage de texture.
  • Il peut être utilisé pour rechercher une base de données.
  • La recherche binaire est plus rapide que la recherche linéaire, en particulier pour les grands tableaux.
  • Plus efficace que d'autres algorithmes de recherche avec une complexité temporelle similaire, tels que la recherche par interpolation ou la recherche exponentielle.
  • La recherche binaire est bien adaptée à la recherche de grands ensembles de données stockés dans une mémoire externe, comme sur un disque dur ou dans le cloud.
  • Le tableau doit être trié.
  • La recherche binaire nécessite que la structure de données recherchée soit stockée dans des emplacements de mémoire contigus.
  • La recherche binaire nécessite que les éléments du tableau soient comparables, c'est-à-dire qu'ils doivent pouvoir être ordonnés.

Foire aux questions (FAQ) sur la recherche binaire :

1. Qu'est-ce que la recherche binaire ?

La recherche binaire est un algorithme efficace pour trouver une valeur cible dans un tableau trié. Cela fonctionne en divisant à plusieurs reprises l’intervalle de recherche en deux.

convertir nfa en dfa

2. Comment fonctionne la recherche binaire ?

La recherche binaire compare la valeur cible à l'élément central du tableau. S'ils sont égaux, la recherche est réussie. Si la cible est inférieure à l'élément du milieu, la recherche continue dans la moitié inférieure du tableau. Si la cible est plus grande, la recherche se poursuit dans la moitié supérieure. Ce processus se répète jusqu'à ce que la cible soit trouvée ou que l'intervalle de recherche soit vide.

3. Quelle est la complexité temporelle de la recherche binaire ?

La complexité temporelle de la recherche binaire est O(log2n), où n est le nombre d’éléments du tableau. En effet, la taille de l'intervalle de recherche est réduite de moitié à chaque étape.

4. Quelles sont les conditions préalables à la recherche binaire ?

La recherche binaire nécessite que le tableau soit trié par ordre croissant ou décroissant. Si le tableau n'est pas trié, nous ne pouvons pas utiliser la recherche binaire pour rechercher un élément dans le tableau.

5. Que se passe-t-il si le tableau n'est pas trié pour la recherche binaire ?

Si le tableau n'est pas trié, la recherche binaire peut renvoyer des résultats incorrects. Il s'appuie sur la nature triée du tableau pour prendre des décisions sur la moitié du tableau à rechercher.

6. La recherche binaire peut-elle être appliquée à des données non numériques ?

Oui, la recherche binaire peut être appliquée à des données non numériques tant qu'il existe un ordre défini pour les éléments. Par exemple, il peut être utilisé pour rechercher des chaînes par ordre alphabétique.

7. Quels sont les inconvénients courants de la recherche binaire ?

L'inconvénient de la recherche binaire est que le tableau d'entrée doit être trié pour décider dans quelle moitié de l'élément cible peut se trouver. Par conséquent, pour les tableaux non triés, nous devons trier le tableau avant d'appliquer la recherche binaire.

8. Quand faut-il utiliser la recherche binaire ?

La recherche binaire doit être utilisée lors de la recherche d'une valeur cible dans un tableau trié, en particulier lorsque la taille du tableau est grande. Il est particulièrement efficace pour les grands ensembles de données par rapport aux algorithmes de recherche linéaire.

9. La recherche binaire peut-elle être implémentée de manière récursive ?

Oui, la recherche binaire peut être implémentée de manière itérative et récursive. L'implémentation récursive conduit souvent à un code plus concis mais peut entraîner une surcharge légèrement plus élevée en raison de l'espace de pile récursif ou des appels de fonction.

10. La recherche binaire est-elle toujours le meilleur choix pour effectuer une recherche dans un tableau trié ?

Bien que la recherche binaire soit très efficace pour rechercher dans des tableaux triés, il peut y avoir des cas spécifiques où d'autres algorithmes de recherche sont plus appropriés, par exemple lorsqu'il s'agit de petits ensembles de données ou lorsque le tableau est fréquemment modifié.

Articles Liés:

  • Recherche binaire sur le didacticiel de réponse avec des problèmes
  • Recherche linéaire vs recherche binaire
  • Comment identifier et résoudre les problèmes de recherche binaire ?