I rewrote my implementation, and it turns out it works if you consider that there are no structs and you compare directly the keys, that could in fact even overlap. (i.e don’t check bounds, consider NumStruct as NumKey, StructSize as DistanceBetweenKeys, with the first key at Start + KeyOffset.)
The information about structs is only needed when returning the index of the found struct at the end.
If that’s the intended way of doing, then the spec is a bit misleading, since it explicitely says:
Within each struct, there is a key value KeySize bytes long, starting at position KeyOffset (from the start of the structure.)