Brainless is not looking for pubkey #110; he is looking for #120's pubkey inside 2^110 range via shifting #120's pubkey. Ultimately he has shrank the range by a factor of 2^10 = 1024 but needs to run the program for each pubkey or integrate runs with the 260 pubkeys.
I believe that for more chances to find a private key, you could shift the range down even more, like to 2^70 but you have 2 million targets.
2 million is about 2^21 targets and birthday reduces the probability of a hit to 2^35, 50% of the keyspace which makes an average of almost 2^21 * 2^35 = nearly 2^56 operations. That's lower than 260 keys at 2^110 keyspace. So I think that it's possible to optimize how much you shift down by adjusting the number of targets and the resulting keyspace size to minimize ops = keyspace/2 + log2_numberoftargets.