Saltar búsqueda

1. Algoritmo de búsqueda por salto
2. Ejemplo de búsqueda con salto
3. Implementación del Algoritmo de Búsqueda por Salto
4. Saltar la complejidad del algoritmo de búsqueda

Jump Search es un algoritmo de búsqueda por intervalos. Es un algoritmo relativamente nuevo que funciona solo en matrices ordenadas. Intenta reducir el número de comparaciones requeridas que la búsqueda lineal al no escanear cada elemento como la búsqueda lineal. En la búsqueda por salto, el array se divide en bloques m. Busca el elemento en un bloque y, si el elemento no está presente, pasa al siguiente bloque. Cuando el algoritmo encuentra el bloque que contiene el elemento, utiliza el algoritmo de búsqueda lineal para encontrar el índice exacto. Este algoritmo es más rápido que la búsqueda lineal pero más lento que la búsqueda binaria.

Algoritmo de búsqueda por salto

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

Ejemplo de búsqueda con salto

Supongamos que tenemos el array: (1, 2, 3, 4, 5, 6, 7, 8, 9), y queremos encontrar X - 7.

Como hay 9 elementos, tenemos n como 9.

Implementación del Algoritmo de Búsqueda por Salto

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

int jumpSearch(int arr[], int x, int n) {
  int m = sqrt(n);
  int i = 0;
  while (arr[min(m, n) - 1] < x) {
    i = m;
    m += sqrt(n);
    if (i >= n) return -1;
  }
  while (arr[i] < x) {
    i++;
    if (i == min(m, n)) return -1;
  }
  if (arr[i] == x) return i;

  return -1;
}

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

Saltar la complejidad del algoritmo de búsqueda

Complejidad del tiempo

• Caso promedio

El algoritmo de clasificación de salto se ejecuta n / m veces donde n es el número de elementos y m es el tamaño del bloque. La búsqueda lineal requiere comparaciones m-1 haciendo que la expresión de tiempo total sea n / m + m-1. El valor más óptimo de m minimizando la expresión de tiempo es √n, haciendo que la complejidad de tiempo sea n/√n + √n, es decir, √n. La complejidad de tiempo del algoritmo Jump Search 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 hacemos saltos n/m, y el último valor que comprobamos es mayor que el elemento que estamos buscando, y se realizan comparaciones m-1 para búsqueda lineal. La complejidad de tiempo en el peor de los casos es O(√n).

Complejidad espacial

La complejidad espacial de este algoritmo es O(1) porque no requiere ninguna estructura de datos más que variables temporales.