Algoritmi za pretragu - Jump search

#include <iostream>
#include <cmath> // zbog sqrt
#include <algorithm> // zbog min
using namespace std;

int JumpSearch(int A[], int n, int x)
{
    // Broj za koji skacemo u jednom koraku
    int step=sqrt(n);

    int start=0;

    // Trazenje bloka u kojem se element nalazi
    while (A[min(step,n)-1]<x)
    {
        start=step; // pamtimo odakle je poceo skok
        step=step+sqrt(n); // skacemo na sljedeci blok

        if (start>=n)
            return -1; // nema elementa
    }

    // linearna pretraga za blok u kome se element nalazi
    while (A[start]<x)
    {
        start++; // povecavamo start

        // ako smo presli cijeli iterval ili dosli do kraja niza
        // u tom slucaju traznog elementa nema pa vracamo -1
        if (start==min(step,n))
            return -1;
    }

    // provjeravamo sljedeci element
    if (A[start]==x)
        return start;

    return -1; // nema elementa
}

int main()
{
    int n,x;
    cin>>n; // broj elemenata niza

    int A[n];

    for (int i=0;i<n;i++)
        cin>>A[i]; // unos niza

    cin>>x; // element koji trazimo

    int res=JumpSearch(A,n,x); // pozivamo funkciju

    if (res==-1) cout<<"U nizu nema trazenog broja"<<endl; // nema elementa
    else cout<<"Broj se nalazi na poziciji "<<res<<endl; // ima elementa

    return 0;
}