binary search algorithm java implementation examples
Ce didacticiel expliquera la recherche binaire et la recherche binaire récursive en Java avec ses exemples d'algorithme, d'implémentation et de code Java Binary Seach:
Une recherche binaire en Java est une technique utilisée pour rechercher une valeur ou une clé ciblée dans une collection. C'est une technique qui utilise la technique du «diviser pour conquérir» pour rechercher une clé.
La collection sur laquelle la recherche binaire doit être appliquée pour rechercher une clé doit être triée par ordre croissant.
Habituellement, la plupart des langages de programmation prennent en charge la recherche linéaire, la recherche binaire et les techniques de hachage utilisées pour rechercher des données dans la collection. Nous apprendrons le hachage dans nos tutoriels ultérieurs.
=> Visitez ici pour apprendre Java à partir de zéro.
Ce que vous apprendrez:
Recherche binaire en Java
La recherche linéaire est une technique de base. Dans cette technique, le tableau est parcouru séquentiellement et chaque élément est comparé à la clé jusqu'à ce que la clé soit trouvée ou que la fin du tableau soit atteinte.
La recherche linéaire est rarement utilisée dans les applications pratiques. La recherche binaire est la technique la plus fréquemment utilisée car elle est beaucoup plus rapide qu'une recherche linéaire.
Java propose trois méthodes pour effectuer une recherche binaire:
lequel des éléments suivants n'est pas une condition décrivant un cas de test?
- Utiliser l'approche itérative
- Utiliser une approche récursive
- Utilisation de la méthode Arrays.binarySearch ().
Dans ce tutoriel, nous allons implémenter et discuter de ces 3 méthodes.
Algorithme pour la recherche binaire en Java
Dans la méthode de recherche binaire, la collection est divisée en deux à plusieurs reprises et l'élément clé est recherché dans la moitié gauche ou droite de la collection selon que la clé est inférieure ou supérieure à l'élément central de la collection.
Un algorithme de recherche binaire simple est le suivant:
- Calculez l'élément central de la collection.
- Comparez les éléments clés avec l'élément central.
- Si clé = élément central, nous retournons la position d'index médiane de la clé trouvée.
- Sinon Si key> mid element, alors la clé se trouve dans la moitié droite de la collection. Répétez donc les étapes 1 à 3 sur la moitié inférieure (droite) de la collection.
- Sinon clé
Comme vous pouvez le voir dans les étapes ci-dessus, dans la recherche binaire, la moitié des éléments de la collection sont ignorés juste après la première comparaison.
Notez que la même séquence d'étapes est valable pour la recherche binaire itérative et récursive.
Illustrons l'algorithme de recherche binaire à l'aide d'un exemple.
Par exemple, prenez le tableau trié suivant de 10 éléments.
Calculons l’emplacement central du tableau.
Milieu = 0 + 9/2 = 4
# 1) Clé = 21
Tout d'abord, nous comparerons la valeur clé avec l'élément (mid) et nous trouvons que la valeur de l'élément à mid = 21.
Ainsi, nous trouvons que key = (mid). Par conséquent, la clé se trouve à la position 4 dans le tableau.
# 2) Clé = 25
Nous comparons d'abord la valeur clé à mid. Comme (21<25), we will directly search for the key in the upper half of the array.
Maintenant, nous trouverons à nouveau le milieu de la moitié supérieure du tableau.
Milieu = 4 + 9/2 = 6
La valeur à l'emplacement (mid) = 25
meilleur moyen de télécharger de youtube en mp3
Maintenant, nous comparons l'élément clé avec l'élément central. Donc (25 == 25), nous avons donc trouvé la clé à l'emplacement (mid) = 6.
Ainsi, nous divisons le tableau à plusieurs reprises et en comparant l'élément clé avec le milieu, nous décidons dans quelle moitié rechercher la clé. La recherche binaire est plus efficace en termes de temps et d'exactitude et est également beaucoup plus rapide.
Implémentation de recherche binaire Java
En utilisant l'algorithme ci-dessus, implémentons un programme de recherche binaire en Java en utilisant l'approche itérative. Dans ce programme, nous prenons un exemple de tableau et effectuons une recherche binaire sur ce tableau.
import java.util.*; class Main{ public static void main(String args()){ int numArray() = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray(mid) last ){ System.out.println('Element is not found!'); } } } Production:
Le tableau d'entrée: (5, 10, 15, 20, 25, 30, 35)
Clé à rechercher = 20
L'élément se trouve à l'index: 3
Le programme ci-dessus montre une approche itérative de la recherche binaire. Au départ, un tableau est déclaré, puis une clé à rechercher est définie.
Après avoir calculé le milieu du tableau, la clé est comparée à l'élément milieu. Ensuite, selon que la clé est inférieure ou supérieure à la clé, la clé est recherchée dans la moitié inférieure ou supérieure du tableau respectivement.
Recherche binaire récursive en Java
Vous pouvez également effectuer une recherche binaire en utilisant la technique de récursivité. Ici, la méthode de recherche binaire est appelée de manière récursive jusqu'à ce que la clé soit trouvée ou que la liste entière soit épuisée.
Le programme qui implémente une recherche binaire récursive est donné ci-dessous:
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray(), int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray(mid) return mid if (intArray(mid) == key){ return mid; } //if intArray(mid) > key then key is in left half of array if (intArray(mid) > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args()){ //define array and key int intArray() = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } } Production:
Liste d'entrée: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
La clé à rechercher:
La clé se trouve à l'emplacement: 3 dans la liste
Utilisation de la méthode Arrays.binarySearch ().
La classe Arrays en Java fournit une méthode «binarySearch ()» qui effectue la recherche binaire sur le tableau donné. Cette méthode prend le tableau et la clé à rechercher comme arguments et renvoie la position de la clé dans le tableau. Si la clé n'est pas trouvée, la méthode renvoie -1.
L'exemple ci-dessous implémente la méthode Arrays.binarySearch ().
import java.util.Arrays; class Main{ public static void main(String args()){ //define an array int intArray() = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } } Production:
Le tableau d'entrée: (10, 20, 30, 40, 50, 60, 70, 80, 90)
La clé à rechercher: 50
La clé se trouve à l'index: 4 dans le tableau.
Questions fréquemment posées
Q # 1) Comment écrivez-vous une recherche binaire?
Répondre: La recherche binaire est généralement effectuée en divisant le tableau en deux. Si la clé à rechercher est supérieure à l'élément médian, alors la moitié supérieure du tableau est recherchée en divisant et en recherchant davantage le sous-tableau jusqu'à ce que la clé soit trouvée.
De même, si la clé est inférieure à l'élément médian, la clé est recherchée dans la moitié inférieure du tableau.
Q # 2) Où la recherche binaire est-elle utilisée?
Répondre: La recherche binaire est principalement utilisée pour rechercher des données triées dans les applications logicielles, en particulier lorsque l'espace mémoire est compact et limité.
ouverture de fichiers .jar sous Windows 10
Q # 3) Quel est le grand O de la recherche binaire?
Répondre: La complexité temporelle de la recherche binaire est O (logn) où n est le nombre d'éléments dans le tableau. La complexité spatiale de la recherche binaire est O (1).
Q # 4) La recherche binaire est-elle récursive?
Répondre: Oui. Puisque la recherche binaire est un exemple de stratégie de division et de conquête et qu'elle peut être implémentée en utilisant la récursivité. Nous pouvons diviser le tableau en deux et appeler la même méthode pour effectuer la recherche binaire encore et encore.
Q # 5) Pourquoi cela s'appelle une recherche binaire?
Répondre: L'algorithme de recherche binaire utilise une stratégie de division et de conquête qui coupe à plusieurs reprises le tableau en deux ou en deux parties. Ainsi, il est nommé recherche binaire.
Conclusion
La recherche binaire est la technique de recherche fréquemment utilisée en Java. La condition requise pour qu'une recherche binaire soit effectuée est que les données doivent être triées par ordre croissant.
Une recherche binaire peut être implémentée en utilisant une approche itérative ou récursive. La classe Arrays en Java fournit également la méthode «binarySearch» qui effectue une recherche binaire sur un Array.
Dans nos tutoriels suivants, nous explorerons diverses techniques de tri en Java.
=> Regardez la série de formation Java simple ici.
lecture recommandée
- Tri par sélection en Java - Algorithme de tri par sélection et exemples
- Tri par insertion en Java - Algorithme de tri par insertion et exemples
- Arbre de recherche binaire C ++: implémentation et opérations BST avec des exemples
- Tutoriel sur l'interface Java et les classes abstraites avec des exemples
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
- Tri à bulles en Java - Algorithmes de tri Java et exemples de code
- Tutoriel Java String | Méthodes de chaîne Java avec exemples
- Qu'est-ce que le vecteur Java | Tutoriel de classe vectorielle Java avec des exemples