Implémentation de recherche binaire (récursive et itérative) dans un programme C-C++-php.cn

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

WBOY

Libérer： 2023-08-26 14:37:11

avant

965 Les gens l'ont consulté

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 &lsquo;element found&rsquo; 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.

Copier après la connexion

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;
}

Copier après la connexion

Output

Element found at index : 4

Copier après la connexion

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;
}

Copier après la connexion