Salto de búsqueda

Al igual que Binary Search , Jump Search es un algoritmo de búsqueda de arrays ordenadas. La idea básica es comprobar menos elementos (que la búsqueda lineal ) avanzando en pasos fijos o omitiendo algunos elementos en lugar de buscar todos los elementos.
Por ejemplo, supongamos que tenemos una array arr[] de tamaño n y un bloque (a saltar) de tamaño m. Luego buscamos en los índices arr[0], arr[m], arr[2m]…..arr[km] y así sucesivamente. Una vez que encontramos el intervalo (arr[km] < x < arr[(k+1)m]), realizamos una operación de búsqueda lineal desde el índice km para encontrar el elemento x.
Consideremos la siguiente array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). La longitud de la array es 16. La búsqueda de salto encontrará el valor de 55 con los siguientes pasos, suponiendo que el tamaño del bloque que se saltará es 4. 
PASO 1: salte del índice 0 al índice 4; 
PASO 2: Saltar del índice 4 al índice 8; 
PASO 3: Saltar del índice 8 al índice 12; 
PASO 4: Dado que el elemento en el índice 12 es mayor que 55, retrocederemos un paso para llegar al índice 8. 
PASO 5: Realice una búsqueda lineal desde el índice 8 para obtener el elemento 55.

Rendimiento en comparación con la búsqueda lineal y binaria:

Si lo comparamos con la búsqueda lineal y binaria, resulta que es mejor que la búsqueda lineal pero no mejor que la búsqueda binaria.

// C++ program to implement Jump Search
  
#include <bits/stdc++.h>
using namespace std;
  
int jumpSearch(int arr[], int x, int n)
{
    // Finding block size to be jumped
    int step = sqrt(n);
  
    // Finding the block where element is
    // present (if it is present)
    int prev = 0;
    while (arr[min(step, n)-1] < x)
    {
        prev = step;
        step += sqrt(n);
        if (prev >= n)
            return -1;
    }
  
    // Doing a linear search for x in block
    // beginning with prev.
    while (arr[prev] < x)
    {
        prev++;
  
        // If we reached next block or end of
        // array, element is not present.
        if (prev == min(step, n))
            return -1;
    }
    // If element is found
    if (arr[prev] == x)
        return prev;
  
    return -1;
}
  
// Driver program to test function
int main()
{
    int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                34, 55, 89, 144, 233, 377, 610 };
    int x = 55;
    int n = sizeof(arr) / sizeof(arr[0]);
      
    // Find the index of 'x' using Jump Search
    int index = jumpSearch(arr, x, n);
  
    // Print the index where 'x' is located
    cout << "\nNumber " << x << " is at index " << index;
    return 0;
}
  
// Contributed by nuclode

#include<stdio.h>
#include<math.h>
int min(int a, int b){
    if(b>a)
      return a;
      else
      return b;
}
int jumpsearch(int arr[], int x, int n)
{
      // Finding block size to be jumped
    int step = sqrt(n);
  
    // Finding the block where element is
    // present (if it is present)
    int prev = 0;
    while (arr[min(step, n)-1] < x)
    {
        prev = step;
        step += sqrt(n);
        if (prev >= n)
            return -1;
    }
  
    // Doing a linear search for x in block
    // beginning with prev.
    while (arr[prev] < x)
    {
        prev++;
  
        // If we reached next block or end of
        // array, element is not present.
        if (prev == min(step, n))
            return -1;
    }
    // If element is found
    if (arr[prev] == x)
        return prev;
  
    return -1;
}
int main()
{
    int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
    int x = 55;
    int n = sizeof(arr)/sizeof(arr[0]);
    int index = jumpsearch(arr, x, n);
    if(index >= 0)
    printf("Number is at %d index",index);
    else
    printf("Number is not exist in the array");
    return 0;
}
  
// This code is contributed by Susobhan Akhuli

// Java program to implement Jump Search.
public class JumpSearch
{
    public static int jumpSearch(int[] arr, int x)
    {
        int n = arr.length;
  
        // Finding block size to be jumped
        int step = (int)Math.floor(Math.sqrt(n));
  
        // Finding the block where element is
        // present (if it is present)
        int prev = 0;
        while (arr[Math.min(step, n)-1] < x)
        {
            prev = step;
            step += (int)Math.floor(Math.sqrt(n));
            if (prev >= n)
                return -1;
        }
  
        // Doing a linear search for x in block
        // beginning with prev.
        while (arr[prev] < x)
        {
            prev++;
  
            // If we reached next block or end of
            // array, element is not present.
            if (prev == Math.min(step, n))
                return -1;
        }
  
        // If element is found
        if (arr[prev] == x)
            return prev;
  
        return -1;
    }
  
    // Driver program to test function
    public static void main(String [ ] args)
    {
        int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                    34, 55, 89, 144, 233, 377, 610};
        int x = 55;
  
        // Find the index of 'x' using Jump Search
        int index = jumpSearch(arr, x);
  
        // Print the index where 'x' is located
        System.out.println("\nNumber " + x +
                            " is at index " + index);
    }
}

# Python3 code to implement Jump Search
import math
  
def jumpSearch( arr , x , n ):
      
    # Finding block size to be jumped
    step = math.sqrt(n)
      
    # Finding the block where element is
    # present (if it is present)
    prev = 0
    while arr[int(min(step, n)-1)] < x:
        prev = step
        step += math.sqrt(n)
        if prev >= n:
            return -1
      
    # Doing a linear search for x in 
    # block beginning with prev.
    while arr[int(prev)] < x:
        prev += 1
          
        # If we reached next block or end 
        # of array, element is not present.
        if prev == min(step, n):
            return -1
      
    # If element is found
    if arr[int(prev)] == x:
        return prev
      
    return -1
  
# Driver code to test function
arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21,
    34, 55, 89, 144, 233, 377, 610 ]
x = 55
n = len(arr)
  
# Find the index of 'x' using Jump Search
index = jumpSearch(arr, x, n)
  
# Print the index where 'x' is located
print("Number" , x, "is at index" ,"%.0f"%index)
  
# This code is contributed by "Sharad_Bhardwaj".

// C# program to implement Jump Search.
using System;
public class JumpSearch
{
    public static int jumpSearch(int[] arr, int x)
    {
        int n = arr.Length;
  
        // Finding block size to be jumped
        int step = (int)Math.Sqrt(n);
  
        // Finding the block where element is
        // present (if it is present)
        int prev = 0;
        while (arr[Math.Min(step, n)-1] < x)
        {
            prev = step;
            step += (int)Math.Sqrt(n);
            if (prev >= n)
                return -1;
        }
  
        // Doing a linear search for x in block
        // beginning with prev.
        while (arr[prev] < x)
        {
            prev++;
  
            // If we reached next block or end of
            // array, element is not present.
            if (prev == Math.Min(step, n))
                return -1;
        }
  
        // If element is found
        if (arr[prev] == x)
            return prev;
  
        return -1;
    }
  
    // Driver program to test function
    public static void Main()
    {
        int[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                    34, 55, 89, 144, 233, 377, 610};
        int x = 55;
  
        // Find the index of 'x' using Jump Search
        int index = jumpSearch(arr, x);
  
        // Print the index where 'x' is located
        Console.Write("Number " + x +
                            " is at index " + index);
    }
}

<?php 
// PHP program to implement Jump Search
  
function jumpSearch($arr, $x, $n)
{
    // Finding block size to be jumped
    $step = sqrt($n);
  
    // Finding the block where element is
    // present (if it is present)
    $prev = 0;
    while ($arr[min($step, $n)-1] < $x)
    {
        $prev = $step;
        $step += sqrt($n);
        if ($prev >= $n)
            return -1;
    }
  
    // Doing a linear search for x in block
    // beginning with prev.
    while ($arr[$prev] < $x)
    {
        $prev++;
  
        // If we reached next block or end of
        // array, element is not present.
        if ($prev == min($step, $n))
            return -1;
    }
    // If element is found
    if ($arr[$prev] == $x)
        return $prev;
  
    return -1;
}
  
// Driver program to test function
$arr = array( 0, 1, 1, 2, 3, 5, 8, 13, 21,
                34, 55, 89, 144, 233, 377, 610 );
$x = 55;
$n = sizeof($arr) / sizeof($arr[0]);
      
// Find the index of '$x' using Jump Search
$index = jumpSearch($arr, $x, $n);
  
// Print the index where '$x' is located
echo "Number ".$x." is at index " .$index;
return 0;
?>

<script>
// Javascript program to implement Jump Search
  
function jumpSearch(arr, x, n) 
{ 
    // Finding block size to be jumped 
    let step = Math.sqrt(n); 
    
    // Finding the block where element is 
    // present (if it is present) 
    let prev = 0; 
    while (arr[Math.min(step, n)-1] < x) 
    { 
        prev = step; 
        step += Math.sqrt(n); 
        if (prev >= n) 
            return -1; 
    } 
    
    // Doing a linear search for x in block 
    // beginning with prev. 
    while (arr[prev] < x) 
    { 
        prev++; 
    
        // If we reached next block or end of 
        // array, element is not present. 
        if (prev == Math.min(step, n)) 
            return -1; 
    } 
    // If element is found 
    if (arr[prev] == x) 
        return prev; 
    
    return -1; 
} 
  
// Driver program to test function 
let arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 
                34, 55, 89, 144, 233, 377, 610]; 
let x = 55; 
let n = arr.length; 
        
// Find the index of 'x' using Jump Search 
let index = jumpSearch(arr, x, n); 
    
// Print the index where 'x' is located 
document.write(`Number ${x} is at index ${index}`); 
    
// This code is contributed by _saurabh_jaiswal
</script>