Explicación de la búsqueda lineal

¿Qué es la búsqueda lineal?

Suponga que le dan una lista o una matriz de elementos. Está buscando un artículo en particular. ¿Cómo haces eso?

Encuentra el número 13 en la lista dada.

Búsqueda lineal 1

¡Basta mirar la lista y ahí está!

Búsqueda lineal 2

Ahora, ¿cómo le dices a una computadora que lo encuentre?

Una computadora no puede mirar más que el valor en un momento dado. Por lo tanto, toma un elemento de la matriz y verifica si es el mismo que está buscando.

Búsqueda lineal 3

El primer elemento no coincidió. Así que pasa al siguiente.

Búsqueda lineal 4

Y así…

Esto se hace hasta que se encuentre una coincidencia o hasta que se hayan verificado todos los elementos.

Búsqueda lineal 5

En este algoritmo, puede detenerse cuando se encuentra el elemento y luego no es necesario buscar más.

Entonces, ¿cuánto tiempo llevaría realizar la operación de búsqueda lineal? En el mejor de los casos, podría tener suerte y el elemento que está mirando quizás esté en la primera posición de la matriz.

Pero en el peor de los casos, tendría que mirar todos y cada uno de los elementos antes de encontrar el elemento en el último lugar o antes de darse cuenta de que el elemento no está en la matriz.

La complejidad de la búsqueda lineal es por tanto O (n).

Si el elemento a buscar viviera en el primer bloque de memoria, entonces la complejidad sería: O (1).

El código para una función de búsqueda lineal en JavaScript se muestra a continuación. Esta función devuelve la posición del elemento que estamos buscando en la matriz. Si el elemento no está presente en la matriz, la función devolverá un valor nulo.

Ejemplo 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; }

Ejemplo 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

Ejemplo 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