@mahdiyari commented:
You can get the public key from the signature
Which is exactly the answer I was looking for.
Although an example of this would be quite nice.
Seeing as public keys are sortable a binary search would be O(log n).
Funny how being aggressively wrong always seems to yield the quickest results.
I always find it interesting when I pose these non-existent problems.
Always something to learn.