Lookup with linear probing

Challenge

Look up a key in an open-addressing hash table using linear probing.

Task

Using the same convention as insertion (the value 0 marks an empty slot), implement int table_find(const int *table, int cap, int start, int key) that probes forward from start, wrapping around, and returns the index where key is stored. Return -1 if an empty slot is reached first or all cap slots have been checked.

Input

• table: array of cap ints; a 0 entry means empty.
• cap: the table size.
• start: the index to begin probing from.
• key: the value to search for (assumed non-zero).

Output

int: index where key is found, or -1 if not present.

Example

table={0,7,8,0}, start=1, key=8   ->   2
table={0,7,8,0}, start=1, key=7   ->   1
table={0,7,8,0}, start=1, key=9   ->   -1   (empty slot hit before finding it)

Edge cases

• Hitting an empty (0) slot stops the search and returns -1: the key cannot be stored past a gap.
• After scanning all cap slots without a match, return -1.

Input format

table: cap ints (0 = empty); cap; start in [0, cap); key (non-zero).

Output format

int: index where key is stored, or -1 if absent.

Constraints

Stop at the first empty slot; wrap with modulo and bound the scan by cap.

Starter code

int table_find(const int *table, int cap, int start, int key) {
    /* TODO */
    return -1;
}