Jump search in a sorted array

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define MAX_N 100
int readArray(int a[], int *n, int nonnegative) {
    if (!readInt(n) || *n < 1 || *n > MAX_N) return 0;

MAX_N is 100. readArray receives an array, the caller’s count address, and a flag requesting nonnegative values. Require a count from 1 to 100; return 0 before using an invalid count.

    for (int i = 0; i < *n; ++i)
        if (!readInt(&a[i]) || (nonnegative && a[i] < 0)) return 0;
    return 1;
}

readInt checks each complete integer token. If nonnegative is nonzero, negative elements are also rejected. Return 1 only after every requested element has been accepted.

void printArray(const int a[], int n) {
    printf("Sorted:"); for (int i = 0; i < n; ++i) printf(" %d",a[i]); putchar('\n');
}

printArray reads the first n elements without modifying them. It prints the Sorted label, a space before each value, and a final newline.

int jumpSearch(const int a[], int n, int key) {
    int block = 1; while ((block + 1) * (block + 1) <= n) ++block;
    int start = 0, end = block < n ? block : n;

Compute floor(sqrt(n)) using a small integer loop, then set start to 0 and end to the smaller of block and n. end is an exclusive bound, so end - 1 identifies the block’s final element. The caller guarantees n >= 1.

    while (a[end - 1] < key) {
        start = end; if (start >= n) return -1;
        end = start + block < n ? start + block : n;
    }

Move start to the old end. If it reaches n, no elements remain. Otherwise advance end by one block, capped at n. This avoids reading past the array on the final partial block.

    for (int i = start; i < end && a[i] <= key; ++i) if (a[i] == key) return i;
    return -1;
}

Scan start..end-1 while values have not exceeded key. Return the first encountered equality or -1 if none exists. Ascending order justifies stopping once an element is greater than the target.

/* n, n ascending values, then key. Results use zero-based indexes. */
int main(void) {

The input is n, then n ascending values, then a search key. Found indexes are zero-based, so the first element is index 0.

    int a[MAX_N], n, key;
    if (!readArray(a,&n,0) || !readInt(&key)) return invalid();
    for (int i = 1; i < n; ++i) if (a[i] < a[i - 1]) { puts("Array must be sorted."); return 1; }

Read the count, signed elements and target. Then reject any adjacent descent before calling the search; the search logic relies on ascending order. Equal adjacent elements are permitted.

    int result = jumpSearch(a,n,key);
    if (result < 0) puts("Not found."); else printf("Found at index %d\n",result);
    return 0;
}

Call jumpSearch and save the returned index. Negative means not found; otherwise print the zero-based index. Return success after a completed search, even when the key is absent.