Búsqueda lineal

1. Algoritmo de búsqueda lineal
2. Ejemplo de búsqueda lineal
3. Implementación del algoritmo de búsqueda lineal
4. Complejidad del algoritmo de búsqueda lineal

La búsqueda lineal es el algoritmo de búsqueda más simple. También se llama búsqueda secuencial porque, en este algoritmo, buscamos un elemento atravesando toda el array y comparando cada elemento con el elemento deseado para encontrar una coincidencia. Si se encuentra el elemento deseado, se devuelve el índice o ese elemento; de lo contrario, continuamos buscando hasta agotar el array. También podemos buscar múltiples apariciones de un elemento dentro de un array. Se utiliza principalmente para buscar elementos dentro de un array sin clasificar. No se usa prácticamente porque es mucho más lento que la búsqueda binaria.

Algoritmo de búsqueda lineal

Supongamos que tenemos un array sin clasificar A[] que contiene n elementos, y queremos encontrar un elemento - X.

Ejemplo de búsqueda lineal

Supongamos que tenemos el array: (5, 3, 4, 2, 1, 6).

• Caso 1: Queremos buscar X = 5.

El primer elemento en sí es una coincidencia y devolvemos el índice 0. (Mejor caso)

• Caso 2: Queremos buscar X = 1.

Atravesamos el array y llegamos al índice 4 para encontrar una coincidencia y devolver ese índice. (Caso promedio)

• Caso 3: Queremos buscar X = 9

Atravesamos el array pero no encontramos una coincidencia cuando llegamos al último elemento del array. Devolvemos -1. (Peor de los casos)

Implementación del algoritmo de búsqueda lineal

Algoritmo de búsqueda lineal para una sola coincidencia

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) return i;
  }
  return -1;
}

int main() {
  int n = 5;
  int arr[] = {2, 4, 0, 1, 9};
  int x = 1;
  int result = search(arr, n, x);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index: " << result;
}

Algoritmo de búsqueda lineal para múltiples coincidencias

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
  vector<int> ans;
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      ans.push_back(i);
    }
  }
  return ans;
}

int main() {
  int n = 9;
  int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
  int x = 1;
  vector<int> res = search(arr, n, x);
  if (res.empty()) {
    cout << "Element not found!!";
  } else {
    cout << "Element found at ";
    for (int i = 0; i < res.size(); i++) {
      cout << res[i] << " ";
    }
  }
}

Complejidad del algoritmo de búsqueda lineal

Complejidad del tiempo

• Caso promedio

La complejidad temporal del algoritmo de búsqueda lineal es O(n).

• Mejor caso

La complejidad del tiempo en el mejor de los casos es O(1). Ocurre cuando el elemento a buscar es el primer elemento presente dentro del array.

• Peor caso

El peor de los casos ocurre cuando el elemento que estamos buscando no está presente dentro del array o está en el último índice del array. La complejidad de tiempo en el peor de los casos es O(n).

Complejidad espacial

La complejidad espacial de este algoritmo depende del número de coincidencias y la implementación utilizada. En general, la complejidad del espacio se indica como O(1), pero puede ser mayor si se almacenan múltiples índices coincidentes dentro de un array.