The amount of times you have to search to find the correct key is equal to any other amount of searches:
10th
Last
First
10000th
All have the same chance of being the correct key.
I will admit I don't really know how encryption keys work, because I've never had to, but it would make sense that when trying to guess, well anything, there is going to be a combination, or a number, or whatever you're guessing, that you just happen to guess last.