Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space.
Surely it is just common sense that searching half the space obviously has a 50% chance of finding the right key 
Unfortunately not as common sense as it should be
But you are right. The expression itself is a bit odd.
I just wanted to say that you don't actually have to seach the whole space (because thats what most people believe when they hear they are that much combination).
On average, it is enough to seach 50% of the space.
The maths of the birthday attack suggests that by randomly generating keys (as opposed to sequentially searching the space), the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be:
Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.
Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.
It is not about a 50% chance to find one correct key, but to find '2 same keys'.
~3,458,770 would be the amount of guesses it would take to have a 50% chance for having generated the same key twice.
I'm pretty sure that the Birthday Attack is the reason why VanityGen generates keys randomly rather than sequentially
Actually this should be a reason for vanitygen to not use randomly.
My guess would be that it is just way faster to randomly generate them than to create them sequentially + memory storage and I/O.
And since vanitygen is used to create addresses with a relatively small prefix (compared to the overall length), it probably doesn't make a huge difference.