Algorithme de recherche linéaire et implémentation en C

La recherche linéaire est essentiellement un algorithme de recherche séquentielle.

Dans cet algorithme, l'élément clé est recherché dans le tableau d'entrée donné dans un ordre séquentiel.

Si l'élément clé est trouvé dans le tableau d'entrée, il renvoie l'élément.

Algorithme de recherche linéaire

Linear_Search (Tableau X, Valeur i)

Définissez j sur 1
Si j > n, passez à l'étape 7
Si X[j] == i, passez à l'étape 6
Ensuite, incrémentez j de 1, c'est-à-dire j=j+1
Revenir à l'étape 2
Affichez l'élément i qui se trouve à un index particulier i, puis passez à l'étape 8
Élément d'affichage introuvable dans l'ensemble des éléments d'entrée.
Sortie/Fin

Pseudo-code pour la recherche linéaire

procedure LINEAR_SEARCH (array, key)

   for each item in the array
      if match element == key
         return element's index
      end if
   end for

end procedure

Implémentation de la recherche linéaire en C

Dans un premier temps, il faut mentionner ou accepter l'élément à rechercher auprès de l'utilisateur.
Ensuite, nous créons une boucle for et commençons à rechercher l'élément de manière séquentielle.
Dès que le compilateur rencontre une correspondance, c'est-à-dire array[element] == key value, renvoie l'élément ainsi que sa position dans le tableau.
Si aucune valeur correspondant à l’entrée n’est trouvée, il renvoie -1.

#include <stdio.h> 

int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 
	 
	for (int i = 0; i < size; i++) 
		if (inp_arr[i] == val) 
			return i; 
	return -1; 
} 


int main(void) 
{ 
	int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; 
	int key = 100; 
	int size = 10; 
	int res = LINEAR_SEARCH(arr, size, key); 
	if (res == -1)
	printf("ELEMENT NOT FOUND!!");
    else
    printf("Item is present at index %d", res);
    
	return 0; 
}

Résultat :

Item is present at index 5

Complexité temporelle de la recherche linéaire

La complexité dans le meilleur des cas est O(1) si l'élément est trouvé dans la première itération de la boucle.

La complexité temporelle dans le pire des cas est O(n), si l'élément recherché est trouvé à la fin du tableau, à condition que la taille du tableau soit n.

Conclusion