Index of a substring

Challenge

Find where one string first appears inside another.

Task

Implement int index_of(const char *hay, const char *needle) that returns the 0-based index of the first occurrence of needle within hay, or -1 if needle does not occur. An empty needle matches at index 0. No main — the grader calls it.

Input

A NUL-terminated haystack hay and a NUL-terminated needle needle.

Output

Returns the index of the first match, or -1 if not found.

Example

index_of("hello world", "world")   ->   6
index_of("abc", "ab")              ->   0
index_of("abc", "")                ->   0     (empty needle)
index_of("abc", "xy")              ->   -1

Edge cases

• An empty needle matches at index 0.
• A needle not present returns -1.

Input format

A NUL-terminated haystack hay and needle needle.

Output format

The 0-based index of the first match, or -1 if not found.

Constraints

An empty needle matches at index 0.

Starter code

#include <string.h>

int index_of(const char *hay, const char *needle) {
    /* TODO */
    return -1;
}

Common mistakes

Off-by-one in low/high boundary updates; integer overflow in (low + high) / 2 instead of low + (high - low) / 2; infinite loop when bounds don't progress.

Edge cases to handle

Empty array; target element not present; target at index 0 or index len-1; array with all identical elements.