Implémentation de recherche binaire (récursive et itérative) dans un programme C

Recherche binaire est un algorithme de recherche utilisé pour trouver la position d'un élément (valeur cible) dans un tableau trié. Le tableau doit être trié avant d'appliquer la recherche binaire.

La recherche binaire est également appelée recherche logarithmique, recherche binaire et recherche par semi-intervalle.

Comment ça marche

L'algorithme de recherche binaire fonctionne en comparant l'élément à rechercher avec l'élément central du tableau et exécute le processus requis en fonction du résultat de cette comparaison.

Cas 1 - élément = valeur moyenne, recherchez l'élément et renvoyez l'index.

Cas 2 - élément > valeur moyenne, recherche d'un élément dans un sous-tableau indexé du milieu +1 à n.

Cas 3 - élément

Algorithme

Valeur initiale du paramètre, valeur finale

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

La fonction d'implémentation de l'algorithme de recherche binaire utilise des fonctions d'appel répétées. Cet appel peut être de deux types :

• itératif
• récursif

un appel itératifboucle plusieurs fois le même morceau de code.

Appel récursif appelle la même fonction à plusieurs reprises.

Un programme pour implémenter une recherche binaire à l'aide d'appels itératifs

Exemple

Démonstration

#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
   while (start_index <= end_index){
      int middle = start_index + (end_index- start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] < element)
         start_index = middle + 1;
      else
         end_index = middle - 1;
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 16;
   int found_index = iterativeBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

Output

Element found at index : 4

Un programme pour implémenter une recherche binaire à l'aide d'appels récursifs

Exemple

Démonstration en ligne

#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
   if (end_index >= start_index){
      int middle = start_index + (end_index - start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] > element)
         return recursiveBinarySearch(array, start_index, middle-1, element);
      return recursiveBinarySearch(array, middle+1, end_index, element);
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 9;
   int found_index = recursiveBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

Output

Element found at index : 3

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!