jump_search.c File Reference

Implementation of jump search algorithm. More...

#include <assert.h>
#include <math.h>
#include <stdio.h>

Include dependency graph for jump_search.c:

Macros
#define	min(X, Y)   ((X) < (Y) ? (X) : (Y))
	Macro to return the minimum of two values.

Functions
int	jump_search (const int *arr, int x, size_t n)
	Implement Jump-search algorithm. More...
void	test ()
	Test implementation of the function.
int	main ()
	Main function.

Detailed Description

Implementation of jump search algorithm.

Function Documentation

jump_search()

int jump_search	(	const int *	arr,
		int	x,
		size_t	n
	)

Implement Jump-search algorithm.

Parameters

[in]	arr	Array to search within
	x	value to search for
	n	length of array

Returns

index where the value was found

-1 if value not found

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