If not, what proportion of the entire keyspace does it search?
(*) What about addresses associated with compressed keys?
What I understand it does:
1) Generate a random private key (or increment from the previous random private key)
2) Calculate the corresponding public key from the private key
3) Calculate the corresponding bitcoin address of the public key
4) Compare, if there is a match output else go back to step 1)
Does that help to answer your question or not?