Fibonacci 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 fibonacciSearch(const int a[], int n, int key) {
    int f2 = 0, f1 = 1, f = 1, offset = -1;
    while (f < n) { f2 = f1; f1 = f; f = f1 + f2; }

f2, f1 and f track consecutive Fibonacci values. Increase them until f is at least n. offset = -1 marks the boundary before the initially unexplored array.

    while (f > 1) {
        int i = offset + f2; if (i >= n) i = n - 1;

While the current Fibonacci range is larger than one, test offset + f2, capped at n - 1. Capping makes the comparison safe when the Fibonacci coverage exceeds the actual array length.

        if (a[i] < key) { f = f1; f1 = f2; f2 = f - f1; offset = i; }

Discard positions through i by moving offset to i. Update the Fibonacci sizes to represent the remaining right-side search range.

        else if (a[i] > key) { f = f2; f1 -= f2; f2 = f - f1; }
        else return i;
    }

A larger a[i] reduces the Fibonacci coverage to the left without advancing offset. Equality returns i immediately. The brace closes the shrinking-range loop.

    if (f1 && offset + 1 < n && a[offset + 1] == key) return offset + 1;
    return -1;
}

When one candidate can remain, check its index bound and value. Return its index on equality; otherwise return -1.

/* 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 = fibonacciSearch(a,n,key);
    if (result < 0) puts("Not found."); else printf("Found at index %d\n",result);
    return 0;
}

Call fibonacciSearch 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.