La recherche linéaire en Java a toujours été la méthode de référence pour rechercher un élément dans un tableau. Il recherche chaque élément du tableau de manière séquentielle et est extrêmement facile à mettre en œuvre. Cependant, les lacunes de la recherche linéaire sont évidentes lorsque le tableau en question contient des dizaines de milliers d'éléments. Dans de tels cas, la méthode «diviser pour régner» mise en œuvre par Binary Search est beaucoup plus efficace et préférable pour les programmeurs soucieux de la complexité temporelle et spatiale.
Recherche binaire
Dans la recherche binaire, un tableau est divisé à plusieurs reprises en deux moitiés jusqu'à ce que la clé (l'élément recherché) soit trouvée. La division est virtuelle c'est-à-dire que l'intégrité des données est maintenue. À chaque itération, la valeur médiane du tableau est focalisée. Si la valeur est égale à la clé que nous recherchons, la boucle ou la fonction récursive se termine. Sinon, il continue de tourner en boucle. Si la valeur médiane est supérieure à la clé, la fonction se concentre alors sur la première moitié du tableau et vice versa. Ce processus est répété jusqu'à ce que la clé soit trouvée ou que le tableau entier ait été itéré.
Différence entre la recherche linéaire et binaire
Recherche linéaire |
Recherche binaire |
Recherche séquentiellement dans le tableau |
Divise le tableau en deux moitiés jusqu'à ce que la valeur soit trouvée |
Fonctionne avec n'importe quel tableau |
Fonctionne uniquement avec des tableaux triés |
La complexité est O(N) |
La complexité est O(log2N) |
Peut fonctionner sur des tableaux triés et non triés |
Ne peut être implémenté que sur des tableaux triés. |
Moins complexe à mettre en œuvre |
Plus complexe à mettre en œuvre |
Algorithme de recherche binaire
L'algorithme de recherche binaire est donné ci-dessous.
- Déterminez le premier et le dernier point du tableau. Les points seront ajustés à chaque itération selon le tableau et la clé recherchés.
- Parcourez le tableau et comparez la valeur médiane entre vos premier et dernier points actuels. Dans la première itération, la première et la dernière variable seront les mêmes que celles réelles du tableau.
- Si la clé est supérieure à la valeur médiane, l'indice de cette valeur sera stocké dans la nouvelle variable "Premier".
- Si la clé est inférieure à la valeur médiane, l'index de cette valeur sera stocké dans la variable 'Last'.
- Cette condition est répétée jusqu'à ce que l'une des deux conditions devienne vraie :
- La clé est trouvée.
- L'ensemble du tableau a été itéré.
Le code pour la recherche binaire itérative et la recherche binaire récursive est donné ci-dessous.
Recherche binaire itérative
Le code pour la recherche binaire avec une méthode itérative est donné ci-dessous.
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
int start = 0;
int end = arr.length;
for(int i = 0; iarr[n]){
start = n;
}
else{
end = n;
}
}
return -1;
}
}
Recherche binaire récursive
Le code pour Binary utilisant la récursivité est donné ci-dessous.
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
if(arr[n]==num)
return n;
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
Complexité temporelle
À chaque itération qui passe, le tableau, c'est-à-dire l'espace de recherche, est divisé en deux. Après chaque itération 'm', l'espace de recherche passera à une taille de N/2m. Dans le pire des cas, il ne nous restera qu'un seul élément d'un côté éloigné du tableau. À ce moment, la complexité de la recherche binaire sera k = log2N. La complexité temporelle de la recherche linéaire est O(N) ce qui fait que la recherche binaire est beaucoup plus rapide avec la complexité O(log2N). C'est le principal avantage de l'utilisation de la recherche binaire par rapport à la recherche linéaire.
Complexité spatiale
La recherche binaire utilise trois variables différentes : début, fin et milieu. Ces trois variables sont créées sous forme de pointeurs qui pointent vers l'emplacement mémoire des indices du tableau. Pour cette raison, la recherche binaire est extrêmement efficace avec de l'espace. La complexité spatiale de la recherche binaire itérative est O(1). Pour une implémentation récursive, c'est O(log N).
GO TO FULL VERSION