C Language Practice: Number Search - Jump Search

A New Skill - Jump Search

What is jump search?

Jump search is our new skill. Let's say that there's a number list called array, the total number of elements in array is stored in a variable called total, and the number we're looking for is called check. We'll divide our array into blocks with length m, and then we'll jump to the edge of each block and check if that number is the same as check. Also, as soon as the edge of one block is greater than check, then we'll go back to the start of the block and search each item of it.

• Step 1: Get m, a new variable, and $m={\sqrt {total}}$. m will be our block length.
• Step 2: See if the edge of each block is the same as check. But as soon as the block edge is greater than check, we'll go back to the start of this block.
• Step 3: Surf the block in the array and check each element if it is equal to check.
• Step 4: If after all those steps, we still can't find check, then check is not in this list at all.

This also suits for the train of thought that we're going to use in our code.

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

int jsearch(int array[], int total, int check)
{
    int m, place;
    m = sqrt(total);
    place = m - 1;
    
    while (array[place] < check)
    {
        place += m;
        if (array[place] == check)
        {
            return place + 1;
        }
    }

    for (int i = place + 1 - m; i < place + 1; i++)
    {
        if (array[i] == check)
        {
            return i + 1;
        }
    }

    return -1;
}

int main(void)
{
    int total, check;
    printf("how many numbers do you want to enter?\n");
    scanf("%d", &total);
    int array[total];
    printf("enter your list of numbers here.\n");
    for (int i = 0; i < total; i++)
    {
        scanf("%d", &array[i]);
    }
    printf("which number are you looking for?\n");
    scanf("%d", &check);

    int oput = jsearch(array, total, check);
    if (oput == -1)
    {
        printf("number not found.\n");
        return 0;
    }
    else
    {
        printf("number %d found at position %d.\n", check, oput);
        return 0;
    }
}