Maison > Article > développement back-end > 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.
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
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 :
un appel itératifboucle plusieurs fois le même morceau de code.
Appel récursif appelle la même fonction à plusieurs reprises.
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; }
Element found at index : 4
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; }
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!