C Exercises: Find the position of a target value within a sorted array using Jump search

Last update on December 20 2024 13:08:24 (UTC/GMT +8 hours)

Write a C program to find the position of a target value within a sorted array using Jump search.

Sample Solution:

Sample C Code:

#include <assert.h>
#include <math.h>
# include <stdio.h>
// Macro to find the minimum value between two numbers
#define find_min_val(p, q) ((p) < (q) ? (p) : (q))

// Function to perform jump search in a sorted array
int jump_search(int array_nums[], int array_size, int x)
{
    // Determine the initial jump size using the square root of the array size
    int pos = floor(sqrt(array_size));
    int prev_pos = 0;
    // Jump to the next block while the target element is greater than the last element of the block
    while (array_nums[find_min_val(pos, array_size) - 1] < x)
    {
        prev_pos = pos;
        pos += floor(sqrt(array_size));
        // Check if the previous position is out of bounds
        if (prev_pos >= array_size)
        {
            return -1; // Element not found
        }
    }
    // Perform linear search within the identified block
    while (array_nums[prev_pos] < x)
    {
        prev_pos = prev_pos + 1;
        // Check if the entire array has been searched
        if (prev_pos == find_min_val(pos, array_size))
        {
            return -1; // Element not found
        }
    }
    // Check if the target element is found
    if (array_nums[prev_pos] == x)
    {
        return prev_pos; // Element found at position prev_pos
    }
    return -1; // Element not found
}
// Main function
int main()
{
    int n;
    // Sorted array for jump search
    int array_nums[] = {0, 10, 20, 20, 30, 50, 70, 75, 82, 92, 115, 123, 141, 153, 160, 170};
    size_t array_size = sizeof(array_nums) / sizeof(int);
    // Print the original array
    printf("Original Array: ");
    for (int i = 0; i < array_size; i++) 
        printf("%d ", array_nums[i]);   
    printf("\n");
    // Input a number to search
    printf("Input a number to search: ");
    scanf("%d", &n); 
    // Perform jump search and print the result
    int index = jump_search(array_nums, array_size, n);
    if (index != -1)
        printf("\nElement found at position: %d", index);
    else
        printf("\nElement not found..!");
    // Return 0 to indicate successful execution
    return 0;
}

Sample Output:

Original Array: 0 10 20 20 30 50 70 75 82 92 115 123 141 153 160 170
Input a number to search: 75

Element found at position: 7
--------------------------------
Process exited after 11.13 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program to find the position of a target value within a array using Interpolation search.
Next: Write a C program to find the position of a target value within a array using Linear search.