Recherche linéaire en Java
Recherche linéaire ou recherche séquentielle en Java | La recherche linéaire ou la recherche séquentielle est une méthode pour trouver un élément dans une liste ou un tableau donné. La recherche linéaire ou recherche séquentielle est généralement très simple à mettre en œuvre et est pratique lorsque la liste ne comporte que quelques éléments, ou lors de l'exécution d'une seule recherche dans une liste non ordonnée.
Exemple :-
Tableau = {50, 90, 30, 70, 60} ;
Entrée pour rechercher = 30
Sortie : - 30 trouvées à l'index 2.
Entrée à rechercher =10
Sortie :- 10 introuvable.
Comment fonctionne la recherche linéaire ?
Dans la recherche linéaire, trouve l'index ou l'emplacement de la recherche dans le tableau donné. Il commence la recherche en comparant la clé de recherche et le premier élément du tableau/de la liste. Si le premier élément n'est pas égal à la clé de recherche, il sera comparé avec l'élément suivant, et ainsi de suite jusqu'à ce que la correspondance soit trouvée ou la fin du tableau. Si la correspondance est trouvée, il renvoie son index, sinon il atteindra la fin du tableau ou de la liste, ce qui signifie que la clé de recherche n'est pas disponible.
Comprenons-le à travers un exemple :- Tableau donné ={50, 90, 30, 70, 60} ;
Supposons que la clé de recherche =30 ; Ensuite, parcourez le tableau et comparez avec chaque élément. Le premier élément du tableau est 50, mais 50 n'est pas égal à 30 donc passez à l'élément suivant. L'élément suivant est 90, mais il n'est pas non plus égal à 30 donc passez à l'élément suivant. L'élément suivant du tableau est 30 qui est égal à la clé de recherche 30, par conséquent, renvoie l'index de l'élément actuel du tableau.
C'était la situation où la clé de recherche existe dans le tableau, supposons maintenant que la clé de recherche n'est pas disponible. Supposons que la clé de recherche =10. Parcourez le tableau et comparez avec chaque élément. Il ne correspondra pas à 50, 90, 30, 70, 60 et a finalement atteint la fin du tableau. Renvoie donc -1 ce qui signifie que la clé de recherche n'est pas disponible.
Algorithme de recherche linéaire en Java
La procédure pour trouver un élément dans un tableau ou une liste donnée par recherche linéaire,
a) Prenez le tableau, la taille du tableau et la clé de recherche. Supposons qu'ils soient :- tableau, n et clé
b) Parcourez le tableau.
c) Comparez la clé avec chaque élément.
d) Si la correspondance est trouvée, renvoyez la position .
e) Sinon, répétez le processus jusqu'à la fin du tableau.
f) Après avoir traversé le tableau Si la correspondance n'est pas trouvée, retournez -1.
L'algorithme de recherche linéaire ou séquentielle peut être donné comme ,
linear search(array, n, key) {
i = 0;
while(i < n) {
if(key == array[i])
then return i;
else
i= i + 1;
}
return -1;
}La complexité temporelle de l'algorithme ci-dessus : - O(n)
- Meilleures performances : - O(1) . Lorsque la clé de recherche est présente au premier index/position du tableau, une seule comparaison est requise.
- Performance dans le pire des cas :- O(n) . Lorsque la clé de recherche est présente au dernier index du tableau, elle nécessite N comparaison, où N est la taille du tableau.
Programme de recherche linéaire en Java
Développons maintenant un programme Java pour démontrer l'algorithme de recherche linéaire. Nous développerons une méthode qui recherchera la clé dans le tableau donné en utilisant un algorithme de recherche linéaire.
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[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// find size of array
int size = arr.length;
// linear search
int index = linearSearch(arr, size, 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();
}
public static int linearSearch(int[] arr, int size, int key) {
// traverse through the array
for (int i = 0; i < size; i++) {
if (key == arr[i])
return i;
}
return -1;
}
}Sortie :-
Saisissez la clé de recherche :30
30 Trouvé à l'index =2
Saisissez la clé de recherche :99
99 introuvable.
Utilisation de la propriété Length pour rechercher un élément de tableau
En Java, chaque tableau a une propriété intégrée pour stocker la taille du tableau, et nous pouvons l'obtenir via le array.length donc lors du développement de méthodes dans le langage de programmation Java, il n'est pas nécessaire de transmettre la taille du tableau. Développons le même programme sans passer la taille du tableau.
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[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// linear search
int index = linearSearch(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();
}
public static int linearSearch(int[] arr, int key) {
// traverse through the array
for (int i = 0; i < arr.length; i++) {
if (key == arr[i])
return i;
}
return -1;
}
}Recherche linéaire d'un tableau de chaînes en Java
Prenons un autre exemple en utilisant le tableau String en Java. Description du programme :- Écrivez un programme Java pour trouver un élément dans un tableau de chaînes à l'aide de la recherche linéaire ou de la recherche séquentielle.
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
String str[] = {"Java", "Python", "C++", "HTML", "CSS"};
// read search key
String key = null;
System.out.print("Enter search key: ");
key = scan.next();
// linear search
int index = linearSearch(str, 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();
}
public static int linearSearch(String[] arr, String key) {
// traverse through the array
for (int i = 0; i < arr.length; i++) {
if (key.equals(arr[i]))
return i;
}
return -1;
}
}Sortie :-
Saisissez la clé de recherche :Java
Java trouvé à l'index =0
Saisissez la clé de recherche :HTML
HTML trouvé à l'index =3
Saisissez la clé de recherche :Ruby
Ruby introuvable.
Saisissez la clé de recherche :Spring
Spring not Found.
Recherche linéaire utilisant la récursivité en Java
Une méthode qui contient un appel à elle-même est appelée la méthode. Une technique de définition de la méthode récursive est appelée récursivité. La méthode récursive nous permet de diviser le problème complexe en cas simples simples identiques qui peuvent être manipulés facilement. C'est aussi une technique de programmation informatique bien connue :diviser pour mieux régner.
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[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// linear search
int index = linear(arr, 0, 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();
}
public static int linear(int arr[], int index, int key) {
if (index >= arr.length)
return -1;
else if (arr[index] == key)
return index;
else
return linear(arr, index + 1, key);
}
}Version améliorée
Nous obtenons les performances O(n) dans le pire des cas car nous ne comparons les éléments du tableau que d'un côté. Au lieu d'un côté, si nous comparons les éléments du tableau des deux extrémités, c'est-à-dire de l'avant et du dernier, cela réduira le nombre d'itérations . Comprenons-le à travers un exemple,
Tableau = {10, 20, 30, 40, 50} ;
Clé de recherche = 40 ;
- Dans la première itération, 40 n'est pas égal à 10 (du côté gauche) et 40 n'est pas égal à 50 (du côté droit).
- Dans la deuxième itération, 40 n'est pas égal à 20 (à partir du côté gauche), mais 40 est égal à 40.
- Par conséquent, la clé de recherche se trouve à l'index 3.
La recherche linéaire normale peut le trouver en 4 itérations, mais une recherche linéaire améliorée peut le trouver en seulement 2 itérations.
Java programme pour la recherche linéaire améliorée ci-dessus ,
import java.util.Scanner;
public class Search2 {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
int arr[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// linear search
int index = linearSearch(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();
}
// Method for improved linear search
// if match found then return index of search key else return -1
public static int linearSearch(int arr[], int key) {
int n = arr.length;
for(int i=0, j=n-1; i<=n/2; i++, j--) {
if(key == arr[i])
return i;
if(key == arr[j])
return j;
}
return -1;
}
}Sortie :-
Saisissez la clé de recherche :70
70 Trouvé à l'index =3
La complexité temporelle dans le meilleur des cas est la même que la précédente :- O(1)
La complexité temporelle dans le pire des cas :- O(n/2)
Voir aussi,
- Algorithme de recherche linéaire dans DSA
- Programme C pour la recherche linéaire
- Programme C++ pour la recherche linéaire
- Programme Python pour la recherche linéaire
