Recherche binaire en Java
Recherche binaire en Java | La recherche binaire est un algorithme efficace pour trouver un élément dans une liste triée ou un tableau d'éléments. Parfois, il est également connu sous le nom de recherche à demi-intervalle, recherche logarithmique ou hachage binaire.
État pour utiliser la recherche binaire :- Le tableau doit être trié par ordre croissant.
L'algorithme de recherche binaire ne peut pas être appliqué à des tableaux non triés. Cet algorithme peut être utilisé lorsque le tableau contient des termes apparaissant par ordre croissant de taille (par exemple :si les termes sont des nombres, ils sont répertoriés du plus petit au plus grand ; s'il s'agit de mots, ils sont répertoriés par ordre lexicographique ou alphabétique) . Si le tableau ou la liste n'est pas trié, avant d'appliquer l'algorithme de recherche binaire, triez d'abord le tableau ou la liste.
L'algorithme de recherche binaire peut être écrit de deux manières. Ce sont,
a) Approche récursive
b) Approche itérative
Table des matières
- Recherche binaire en Java à l'aide de la récursivité
- Algorithme de recherche binaire en Java utilisant la récursivité
- Comment fonctionne l'approche récursive ?
- Programme Java pour implémenter la recherche binaire à l'aide de la récursivité
- Recherche binaire en Java à l'aide d'une approche itérative
- Algorithme
- Programme Java
- Méthode Arrays.binarySearch() en Java
- Exemple utilisant Arrays.binarySearch()
- Complexité du temps de recherche binaire
Recherche binaire en Java à l'aide de la récursivité
Dans l'approche récursive, la technique de récursivité est utilisée. C'est un exemple de la technique du « diviser pour régner » où les problèmes plus importants sont divisés en problèmes plus petits. Comme tous les algorithmes de division et de conquête, la recherche binaire divise d'abord le grand tableau en sous-tableaux plus petits, puis le résout de manière récursive. Nous allons le voir en détail.
Algorithme de recherche binaire en Java utilisant la récursivité
a) Prenez un tableau, un index initial, une taille et une clé de recherche.
b) Trouvez le terme moyen.
c) Si terme moyen ==clé de recherche, alors retournez l'index.
d) Si moyen terme> clé de recherche, puis appliquez un appel récursif sur la première moitié du tableau.
e) Sinon, appliquez un appel récursif sur la seconde moitié du tableau.
f) Répétez le processus jusqu'à ce que la clé de recherche ne soit plus correspond.
g) S'il n'y a pas de correspondance, renvoie -1.
La méthode de recherche binaire en Java utilisant la récursivité peut être écrite comme,
int binarySearch(arr, low, high, key) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
return binarySearch(arr, mid + 1, high, key);
}
return -1;
}La complexité temporelle de cet algorithme =O(log n)
Comment fonctionne l'approche récursive pour la recherche binaire ?
Dans la recherche binaire utilisant l'approche récursive, nous divisons le tableau du milieu en deux sous-tableaux de même taille ou lorsque l'une de ces listes plus petites contient un terme de moins que l'autre. Comprenons-le à travers un exemple.
Tableau ={10, 20, 30, 40, 50, 60, 70, 80, 90, 100} ;
Exemple
Supposons que le terme de recherche =40. Ensuite, les étapes de la recherche binaire,
- Trouvez le moyen terme du tableau. Si la taille du tableau est impaire alors middle-index =(size – 1)/2 sinon middle-index =size/2. Dans notre exemple, middle index =10/2 =5, et middle term est array[3] =60
- Comparer le terme moyen et le terme de recherche. Si le terme intermédiaire> terme de recherche, il peut exister dans la première partie du tableau, sinon dans la deuxième partie du tableau. Puisque 60> 40, le terme de recherche ne peut donc exister que dans la première partie du tableau.
- Divisez le tableau en deux parties à partir de l'index du milieu. Le subarr1 ={10, 20, 30, 40, 50} et subarr2 ={60, 70, 80, 90, 100}.
- Étant donné que le tableau est trié et 60> 40, les termes de recherche ne peuvent donc exister que dans le premier sous-tableau. Oublié le deuxième sous-tableau, pas d'utilisation, seul le premier sous-tableau est requis pour l'étape suivante. Supposons maintenant que le tableau d'origine ={10, 20, 30, 40, 50} et le terme de recherche =40.
- Répétez le même processus avec le premier sous-tableau. Trouvez le moyen terme. L'indice du milieu =(5-1)/2 =2, le terme du milieu est array[2] =30
- Comparez le terme moyen avec le terme de recherche, 30 <40 donc il peut n'exister que dans la deuxième partie.
- Diviser le tableau en deux sous-tableaux à partir de l'index du milieu. Les nouveaux sous-tableaux sont :- subarr1 ={10, 20} et subarr2 ={30, 40, 50}. Seul subarr2 sera pris en compte pour les prochaines étapes, pas d'utilisation de subarr1. Maintenant, supposons que array ={30, 40, 50} et le terme de recherche =40. Répétez le processus.
- Trouvez le moyen terme. L'index du milieu =(3-1)/2 =1 et le terme du milieu est array[1] =40.
- Comparer le terme moyen et le terme de recherche. Actuellement, les deux sont égaux et la correspondance est trouvée.
Programme Java pour implémenter la recherche binaire à l'aide de la récursivité
Voyons maintenant l'implémentation de l'algorithme de recherche binaire dans le langage de programmation Java. Ici la méthode binarySearch() trouve l'index de la clé de recherche, si la correspondance est trouvée alors elle retourne l'index de la clé de recherche sinon elle retourne -1.
public class Search {
public static void main(String[] args) {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 40; // search key
// binary search
int index = binarySearch(arr, 0, arr.length, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
}
// Method for binary search
/* if match found then return index of search key
else return -1 */
public static int binarySearch(int[] arr, int low,
int high, int key) {
if (high >= low) {
// find middle index
int mid = low + (high - low) / 2;
// find middle term and compare
if (arr[mid] == key) return mid; // key found
// If key is smaller than middle term, then
// it can only be present in left subarray
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
// Else the key can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, key);
}
// key not found
return -1;
}
}Sortie :-
40 Trouvé à Index =3
Recherche binaire en Java en utilisant l'approche itérative
Dans cette approche, au lieu d'appeler la méthode de manière récursive, nous utilisons l'itération pour parcourir le tableau et trouver la clé de recherche . Les deux approches sont assez similaires, avec deux différences dans la mise en œuvre.
Dans la méthode récursive, il n'y a pas de boucle, et plutôt que de passer les nouvelles valeurs à la prochaine itération de la boucle, il les passe à la prochaine récursivité. Dans la méthode itérative, les itérations peuvent être contrôlées par les conditions de bouclage, tandis que dans la méthode récursive, le maximum et le minimum sont utilisés comme condition aux limites.
Algorithme de recherche binaire en Java utilisant une approche itérative
Pour rechercher l'entier x dans la liste/le tableau a1 , a2 , … ,an , où le tableau est dans l'ordre croissant (a1
- commencer par comparer x avec le moyen terme am de la liste/tableau, où m =⌊(n + 1)/2⌋.
- Si x> am , la recherche de x est limitée à la seconde moitié de la liste, qui est am+1 , unm+2 , …, unn .
- Si x n'est pas supérieur à am , la recherche de x est limitée à la première moitié de la liste, qui est a1 , a2 , …, am .
- La recherche a maintenant été restreinte à une liste ne contenant pas plus de ⌊n/2⌋ éléments.
- En utilisant la même procédure, comparez x au moyen terme de la liste restreinte.
- Ensuite, restreignez la recherche à la première ou à la seconde moitié de la liste.
- Répétez ce processus jusqu'à ce qu'une liste avec un terme soit obtenue.
- Ensuite, déterminez si ce terme est x.
L'algorithme peut être écrit comme,
int binary search (a: array, lowIndex, highIndex, x: search-key) {
i = lowIndex; // i is left endpoint of search interval
j = highIndex; // j is right endpoint of search interval
while (i < j) {
m = (i+j)/2; // floor of (i+j)/2
if (x > a[m] ) then i = m+1;
else j = m;
}
if (x=a[i]) then location = i;
else location = -1;
return location'
}Programme de recherche binaire en Java utilisant une approche itérative
Voyons maintenant le programme Java pour la recherche binaire utilisant l'approche itérative,
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
// read search key
System.out.print("Enter search key: ");
int key = scan.nextInt();
// binary search
int index = binarySearch(arr, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
// close Scanner class object
scan.close();
}
// binary search for complete array
public static int binarySearch(int[] arr, int key) {
// pass 0 as low value, array-size as high value
return binarySearchRange(arr, 0, arr.length, key);
}
// Binary search method for a given range of array
/* if match found then return index of
* search key else return -1
*/
public static int binarySearchRange(int[] arr,
int low, int high, int key) {
int i = low; // left index
int j = high; // right index
int mid = 0;
while (i < j) {
// find middle index
mid = (i + j) / 2;
// compare search key and middle term
if (key > arr[mid])
i = mid + 1;
else
j = mid;
}
// when i==j
if (key == arr[i])
return i; // key found
return -1; // key not found
}
}Sortie :-
Saisissez la clé de recherche :50
50 Trouvé à l'index =4
Saisissez la clé de recherche :88
88 introuvable.
Méthode Arrays.binarySearch() en Java
Lorsque vous travaillez avec le langage de programmation Java, il n'est pas nécessaire d'écrire la logique séparée pour l'algorithme de recherche binaire. Dans la classe java.util.Arrays, nous avons une méthode intégrée appelée binarySearch(). La classe Java Arrays a été introduite dans la version JDK 1.2, qui contient diverses méthodes pour manipuler des tableaux tels que le tri, la recherche, la copie, la conversion d'un tableau en chaîne et etc.
La méthode Arrays.binarySearch() recherche dans le tableau spécifié la valeur spécifiée à l'aide de l'algorithme de recherche binaire. Il utilise une approche itérative, pas la méthode récursive.
Condition pour utiliser la méthode Arrays.binarySearch() :- Le tableau doit être trié par ordre croissant. Si le tableau n'est pas trié, les résultats seront indéfinis.
Si le tableau n'est pas trié, nous pouvons utiliser Arrays.sort() ou Arrays.parallelSort() pour trier le tableau donné dans l'ordre croissant. Si le tableau contient plusieurs éléments avec la valeur spécifiée, rien ne garantit lequel sera trouvé.
Il existe plusieurs formes surchargées de la méthode binarySearch() avec plage ou sans plage.
public static int binarySearch(byte[] a, byte key)public static int binarySearch(short[] a, short key)public static int binarySearch(int[] a, int key)public static int binarySearch(long[] a, long key)public static int binarySearch(float[] a, float key)public static int binarySearch(double[] a, double key)public static int binarySearch(char[] a, char key)public static int binarySearch(Object[] a, Object key)public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)public static int binarySearch(short[] a, int fromIndex, int toIndex, short key)public static int binarySearch(int[] a, int fromIndex, int toIndex, int key)public static int binarySearch(long[] a, int fromIndex, int toIndex, long key)public static int binarySearch(float[] a, int fromIndex, int toIndex, float key)public static int binarySearch(double[] a, int fromIndex, int toIndex, double key)public static int binarySearch(char[] a, int fromIndex, int toIndex, char key)public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
Paramètres dans la méthode binarySearch() :-
- un :- le tableau à rechercher
- de l'index :- l'index du premier élément (inclusif) à rechercher
- toIndex :- l'index du dernier élément (exclusif) à rechercher
- clé :- la valeur à rechercher
Valeur de retour :- Il renvoie l'index de la clé de recherche. Si le tableau ne contient pas de clé, il renvoie -1.
Exemple d'utilisation de Arrays.binarySearch()
Exemple Utilisation de Arrays.binarySearch() de la classe Java Arrays pour rechercher un élément dans un tableau trié donné,
import java.util.Arrays;
public class Search {
public static void main(String[] args) {
// array
int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
// search 85
System.out.println("80 found at index = "
+ Arrays.binarySearch(arr, 80) );
// search 75
if (Arrays.binarySearch(arr, 75) != -1) {
System.out.println("75 Found");
} else {
System.out.println("75 not Found");
}
}
}Sortie :-
80 trouvés à l'index =7
75 trouvés
Si le tableau n'est pas trié par ordre croissant, nous risquons d'obtenir un mauvais résultat. Si le tableau est trié mais dans l'ordre décroissant, nous pouvons également obtenir un mauvais résultat.
import java.util.Arrays;
public class Search {
public static void main(String[] args) {
// array
int arr[] = { 100, 20, 30, 10, 50};
// search 20
System.out.println("20 found at index = "
+ Arrays.binarySearch(arr, 20));
}
}Sortie :-
20 trouvés à index =-1
Par conséquent, si le tableau n'est pas trié, avant d'appeler la méthode Arrays.binarySearch(), triez le tableau donné à l'aide de Arrays.sort() ou Arrays.parallelSort(). Voir :- Comment trier un tableau en Java
import java.util.Arrays;
public class Search {
public static void main(String[] args) {
// array
int arr[] = { 100, 20, 30, 10, 50};
// display intial array
System.out.println("Initial array = "
+ Arrays.toString(arr));
// sort the array
Arrays.sort(arr);
// display array after sorting
System.out.println("Array after Sorting= "
+ Arrays.toString(arr));
// search 20
System.out.println("20 found at index = "
+ Arrays.binarySearch(arr, 20));
}
}Sortie :-
Tableau initial =[100, 20, 30, 10, 50]
Tableau après tri =[10, 20, 30, 50, 100]
20 trouvé à l'index =1
Dans ce programme, pour afficher le tableau, nous avons utilisé la méthode Arrays.toString() qui est donnée pour convertir le tableau en chaîne.
Voyons un autre exemple de programme Java utilisant un algorithme de recherche binaire. Maintenant, nous n'écrivons pas la logique de l'algorithme de recherche binaire. Au lieu de cela, nous appellerons la méthode Arrays.binarySearch() et si nécessaire, nous commencerons par trier le tableau donné.
Description du programme :- Écrivez un programme Java pour rechercher une chaîne dans la liste des chaînes en utilisant un algorithme de recherche binaire.
import java.util.Arrays;
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
// unsorted array of String
String arr[] = {"Java", "HTML", "C++", "Python", "CSS"};
// display initial array
System.out.println("Initial array = "
+ Arrays.toString(arr));
// sort the array
Arrays.sort(arr);
// display array after sorting
System.out.println("Initial array = "
+ Arrays.toString(arr));
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// read character
System.out.print("Enter a string to search: ");
String str = scan.next();
// search character
int index = Arrays.binarySearch(arr, str);
// display result
if(index != -1)
System.out.println(str + " found at index = " + index);
else
System.out.println(str+" not found.");
// close Scanner
scan.close();
}
}Sortie :-
Tableau initial =[Java, HTML, C++, Python, CSS]
Tableau initial =[C++, CSS, HTML, Java, Python]
Entrez une chaîne à rechercher :Java
Java trouvé sur indice =3
Tableau initial =[Java, HTML, C++, Python, CSS]
Tableau initial =[C++, CSS, HTML, Java, Python]
Entrez une chaîne à rechercher :C#
C# introuvable .
Complexité du temps de recherche binaire
| Meilleur cas complexité temporelle | O(1) | Lorsque la clé de recherche est présente au centre (moyen terme) du tableau. |
| Dans le pire des cas complexité temporelle | O(log n) | Lorsque la clé de recherche n'est pas disponible ou à l'extrémité de la liste. |
Dans la méthode itérative, la complexité spatiale serait O(1). Alors que dans la méthode récursive, la complexité spatiale serait O (log n).
Pour les petits tableaux, l'algorithme de recherche linéaire donne de meilleures performances par rapport au tableau binaire, mais pour les grands tableaux, si le tableau est dans un ordre trié, la recherche binaire donne de meilleures performances par rapport à la recherche linéaire.
Il existe des structures de données spécialisées conçues pour une recherche rapide , comme les tables de hachage , qui peut être recherché plus efficacement que la recherche binaire. Cependant, la recherche binaire peut être utilisée pour résoudre un plus large éventail de problèmes, comme trouver l'élément suivant le plus petit ou le plus grand dans le tableau par rapport à la cible même s'il est absent du tableau.
