Scribd
Importer
2 vues1 page

Binary Search

Le document présente une implémentation en C de l'algorithme de recherche binaire, à la fois itérative et récursive. Il définit deux fonctions, 'rechercheBinaire' et 'rechercheBinaireRec', pour trouver la position d'un élément dans un tableau trié. Un exemple d'utilisation est fourni dans la fonction 'main', qui teste la recherche d'un élément spécifique dans un tableau.

Transféré par

Sa Rak
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
2 vues1 page

Binary Search

Le document présente une implémentation en C de l'algorithme de recherche binaire, à la fois itérative et récursive. Il définit deux fonctions, 'rechercheBinaire' et 'rechercheBinaireRec', pour trouver la position d'un élément dans un tableau trié. Un exemple d'utilisation est fourni dans la fonction 'main', qui teste la recherche d'un élément spécifique dans un tableau.

Transféré par

Sa Rak
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

1 #include <stdio.

h>
2
3 int rechercheBinaire(int tab[], int n, int x) {
4 int debut = 0;
5 int fin = n - 1;
6
7 while (debut <= fin) {
8 int milieu = (debut + fin) / 2;
9
10 if (tab[milieu] == x)
11 return milieu; // trouvé
12 else if (tab[milieu] < x)
13 debut = milieu + 1; // chercher à droite
14 else
15 fin = milieu - 1; // chercher à gauche
16 }
17
18 return -1; // non trouvé
19 }
20 //////////////////////////////
21 int rechercheBinaireRec(int tab[], int debut, int fin, int x) {
22 if (debut > fin)
23 return -1; // cas de base : non trouvé
24
25 int milieu = (debut + fin) / 2;
26
27 if (tab[milieu] == x)
28 return milieu; // trouvé
29 else if (tab[milieu] < x)
30 return rechercheBinaireRec(tab, milieu + 1, fin, x); // chercher à droite
31 else
32 return rechercheBinaireRec(tab, debut, milieu - 1, x); // chercher à gauche
33 }
34 ////////////////////////////////
35
36 int main() {
37 int tab[] = {3, 8, 12, 20, 25, 31, 42};
38 int n = sizeof(tab) / sizeof(tab[0]);
39 int x = 25;
40
41 int pos = rechercheBinaire(tab, n, x);
42
43 if (pos != -1)
44 printf("Élément %d trouvé à la position %d\n", x, pos);
45 else
46 printf("Élément %d non trouvé\n", x);
47
48 return 0;
49 }
50

Vous aimerez peut-être aussi