Recherche linéaire en Java

La recherche linéaire en Java est l'un des algorithmes de recherche les plus simples qui permet de rechercher un élément dans la liste dans un ordre séquentiel. Mais la recherche linéaire est rarement utilisée comme les autres algorithmes tels que les algorithmes de recherche binaires, les tables de hachage permettent une recherche plus rapide par rapport à la recherche linéaire. Une recherche séquentielle est effectuée pour chaque élément, c'est-à-dire que chaque élément est vérifié, et si une correspondance est trouvée, alors cet élément est renvoyé ; sinon, la recherche se poursuit jusqu'à la fin de la collecte des données. Il existe des méthodes en Java pour implémenter des opérations de recherche linéaire. Approfondissons cette recherche linéaire et comment elle est implémentée en Java étape par étape avec quelques exemples.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Syntaxe

Comme aucune syntaxe n'est disponible pour les algorithmes de recherche, il y aura un algorithme qui nous aidera à implémenter l'algorithme de recherche linéaire dans n'importe quel langage de programmation.

Algorithme :

Étape 1 : Tout d'abord, nous devons obtenir la longueur du tableau

Étape 2 : Récupérez l'élément qui doit être recherché et stockez-le dans une variable

Étape 3 : Maintenant, comparez chaque élément du tableau avec la valeur consultable

Étape 4 : Si au cas où, il y a une correspondance. Ensuite, l'élément consultable est trouvé

Étape 5 : Sinon, c'est-à-dire si aucune correspondance n'est trouvée. Ensuite, l'élément recherché n'est pas trouvé et renvoie -1 s'il est donné

Comment exécuter un algorithme de recherche linéaire ?

Nous suivrons les étapes algorithmiques ci-dessus pour implémenter manuellement l'algorithme de recherche linéaire avec un exemple, puis passerons aux exemples de programmation.

Exemple :

Laissez le tableau A[4, 8, 2, 3, 6, 9]

Laissez l'élément consultable X=3 ;

4

8

2

3

6

9

Voici le tableau à rechercher X=3 ;

Nous avons besoin de la longueur du tableau lorsque la recherche linéaire est effectuée par programme.

À partir du premier élément

4

8

2

3

6

9

Donc ici X=3 = 4

Comparaison avec d'autres éléments

4

8

2

3

6

9

Donc ici X=3 = 8

Nous, Will, passons à l'élément suivant,

4

8

2

3

6

9

Donc ici X=3 = 2

Allera de l'avant,

4

8

2

3

6

9

Donc ici X=3 = 3

Renverra l'index de l'élément et reviendra. L'indice de l'élément est 3

S'il n'y a aucun élément trouvé jusqu'à la fin du tableau, alors il renverra -1, c'est-à-dire introuvable.

Exemple n°1

Algorithme de recherche linéaire

class LinearSearchAlgorithm {
static int LSA(int array[], int length, int x)
{
for (int i = 0; i < length; i++) {
if (array[i] == x)
return i;
}
return -1;
}
public static void main(String[] args)
{
int[] array = { 4, 8, 2, 3, 6, 9 };
int length = array.length;
int x = 3;
int index = LSA(array, length, x);
if (index == -1)
System.out.println("Element not found in the array");
else
System.out.println("Element is found at index " + index);
}
}

Sortie :

Exemple n°2

import java.util.Scanner;
class LSA
{
public static void main(String args[])
{
int length, k, i, array[];
Scanner input = new Scanner(System.in);
System.out.println("Enter length of the array:");
length = input.nextInt();
array = new int[length];
System.out.println("Enter " + length + " elements");
for (i = 0; i < length; i++)
{
array[i] = input.nextInt();
}
System.out.println("Enter the value to be searched:");
k = input.nextInt();
for (i = 0; i < length; i++)
{
if (array[i]== k)
{
System.out.println(k+" is found at index "+(i));
break;
}
}
if (i == length)
System.out.println(k + " is not found in the array");
}
}

Sortie 1 :

Vous trouverez ci-dessous les entrées données dans l'invite de commande STDIN,

Non. d'éléments du tableau : 6

Éléments du tableau : 2, 4, 6, 8, 10, 1

Valeur consultable : 4

Sortie 2 :

Non. d'éléments du tableau : 8

Éléments du tableau : 3, 5, 7, 9, 10, 34, 25, 21

Valeur consultable : 10

Sortie 3 : Si élément introuvable

Non. d'éléments : 5

Éléments du tableau : 2, 4, 5, 6, 10

Valeur consultable : 9

Complexité temporelle de l'algorithme de recherche linéaire

Comme l'algorithme de recherche linéaire est rarement utilisé, d'autres algorithmes de recherche tels que les tables de hachage et la recherche binaire permettent une recherche rapide. La complexité temporelle de la recherche linéaire est la suivante :

Si un élément est trouvé dans le tableau : O(n) à O(1)

Si l'élément n'est pas trouvé dans le tableau : O(n) à O(n/2)

Avec ceci, nous conclurons notre sujet « Recherche linéaire en Java ». Nous avons vu ce qu'est l'algorithme de recherche linéaire et ses étapes de mise en œuvre avec un exemple. Des exemples ont également été résolus par programme et ont montré diverses sorties, c'est-à-dire lorsque l'élément est disponible et lorsque l'élément n'est pas disponible. Nous avons également vu la complexité temporelle de l'algorithme de recherche linéaire basé sur la valeur consultable si elle est trouvée ou non. Merci! Bon apprentissage !!

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!