It's not going through them one at a time.

By my calculations, if you had the entire earth's surface covered by a solid meter-thick layer of bacteria for 4.6 billion years and each bacterium lived for 1 hour, that would be approximately 2^155 bacteria having lived and died.

You can massively increase genetic information (inasmuch as that actually means much in biology) very quickly with very simple genetic changes. It's not a case of searching through every possible 1 bit change.