Recherche linéaire expliquée

Qu'est-ce que la recherche linéaire?

Supposons que vous receviez une liste ou un tableau d'éléments. Vous recherchez un article en particulier. Comment tu fais ça?

Trouvez le numéro 13 dans la liste donnée.

Recherche linéaire 1

Il suffit de regarder la liste et la voilà!

Recherche linéaire 2

Maintenant, comment dire à un ordinateur de le trouver?

Un ordinateur ne peut pas regarder plus que la valeur à un instant donné. Il prend donc un élément du tableau et vérifie s'il correspond à ce que vous recherchez.

Recherche linéaire 3

Le premier élément ne correspond pas. Alors, passez au suivant.

Recherche linéaire 4

Etc…

Ceci est fait jusqu'à ce qu'une correspondance soit trouvée ou jusqu'à ce que tous les éléments aient été vérifiés.

Recherche linéaire 5

Dans cet algorithme, vous pouvez vous arrêter lorsque l'élément est trouvé et il n'est alors pas nécessaire de chercher plus loin.

Alors, combien de temps faudrait-il pour effectuer l'opération de recherche linéaire? Dans le meilleur des cas, vous pourriez avoir de la chance et l'élément que vous regardez peut-être à la première position du tableau!

Mais dans le pire des cas, vous devrez regarder chaque élément avant de trouver l'élément à la dernière place ou avant de vous rendre compte que l'élément n'est pas dans le tableau.

La complexité de la recherche linéaire est donc O (n).

Si l'élément à rechercher vivait sur le premier bloc mémoire, alors la complexité serait: O (1).

Le code d'une fonction de recherche linéaire en JavaScript est indiqué ci-dessous. Cette fonction renvoie la position de l'élément que nous recherchons dans le tableau. Si l'élément n'est pas présent dans le tableau, la fonction renverra null.

Exemple en Javascript

function linearSearch(arr, item) { // Go through all the elements of arr to look for item. for (var i = 0; i < arr.length; i++) { if (arr[i] === item) { // Found it! return i; } } // Item not found in the array. return null; }

Exemple en Ruby

def linear_search(target, array) counter = 0 while counter < array.length if array[counter] == target return counter else counter += 1 end end return nil end

Exemple en C ++

int linear_search(int arr[],int n,int num) { for(int i=0;i

Example in Python

def linear_search(array, num): for i in range(len(array)): if (array[i]==num): return i return -1

Global Linear Search

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

Target = 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

This array has 3 occurrences of 5s and we want to return the indexes (where they are in the array) of all of them.

This is called global linear search and you will need to adjust your code to return an array of the index points at which it finds your target element.

When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match, the code will continue to move on to the next element in the array by adding 1 to the counter.

def global_linear_search(target, array) counter = 0 results = [] while counter < array.length if array[counter] == target results << counter counter += 1 else counter += 1 end end if results.empty? return nil else return results end end

Why linear search is not efficient

There is no doubt that linear search is simple. But because it compares each element one by one, it is time consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So you should also learn about bubble sort, quick sort and other more efficient algorithms.

Other search algorithms:

  • How to implement quick sort
  • Binary search algorithm
  • Jump search algorithm
  • Search algorithms explained with examples
  • Implement a binary search algorithm in Java without recursion
  • More info on search algorithms

Original text