Dans cet article, nous discuterons de l'algorithme de recherche binaire. La recherche est le processus consistant à trouver un élément particulier dans la liste. Si l'élément est présent dans la liste, alors le processus est appelé réussi et le processus renvoie l'emplacement de cet élément. Sinon, la recherche est dite infructueuse.
La recherche linéaire et la recherche binaire sont les deux techniques de recherche les plus populaires. Ici, nous discuterons de l’algorithme de recherche binaire.
La recherche binaire est la technique de recherche qui fonctionne efficacement sur les listes triées. Par conséquent, pour rechercher un élément dans une liste à l’aide de la technique de recherche binaire, nous devons nous assurer que la liste est triée.
La recherche binaire suit l'approche diviser pour régner dans laquelle la liste est divisée en deux moitiés et l'élément est comparé à l'élément central de la liste. Si la correspondance est trouvée, l'emplacement de l'élément central est renvoyé. Sinon, nous recherchons l'une ou l'autre des mi-temps en fonction du résultat produit par le match.
REMARQUE : la recherche binaire peut être implémentée sur des éléments de tableau triés. Si les éléments de la liste ne sont pas triés, nous devons d’abord les trier.
Voyons maintenant l'algorithme de recherche binaire.
Algorithme
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
Fonctionnement de la recherche binaire
Voyons maintenant le fonctionnement de l'algorithme de recherche binaire.
Pour comprendre le fonctionnement de l'algorithme de recherche binaire, prenons un tableau trié. Il sera facile de comprendre le fonctionnement de la recherche binaire avec un exemple.
Il existe deux méthodes pour implémenter l'algorithme de recherche binaire :
- Méthode itérative
- Méthode récursive
La méthode récursive de recherche binaire suit l’approche diviser pour régner.
Soit les éléments du tableau -
Soit l'élément à rechercher, K = 56
Nous devons utiliser la formule ci-dessous pour calculer le milieu du tableau -
mid = (beg + end)/2
Donc, dans le tableau donné -
mendier = 0
fin = 8
milieu = (0 + 8)/2 = 4. Donc, 4 est le milieu du tableau.
Désormais, l’élément à rechercher est trouvé. L'algorithme renverra donc l'index de l'élément correspondant.
limites de la banque électronique
Complexité de la recherche binaire
Voyons maintenant la complexité temporelle de la recherche binaire dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale de la recherche binaire.
1. Complexité temporelle
| Cas | Complexité temporelle |
|---|---|
| Meilleur cas | O(1) |
| Cas moyen | O (connexion) |
| Pire cas | O (connexion) |
2. Complexité spatiale
| Complexité spatiale | O(1) |
- La complexité spatiale de la recherche binaire est O(1).
Implémentation de la recherche binaire
Voyons maintenant les programmes de recherche binaire dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter la recherche binaire en langage C.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Sortir
Donc, c'est tout à propos de l'article. J'espère que l'article vous sera utile et informatif.