Exposure to UV radiation results in numerous DNA lesions, which threaten genome integrity. The nucleotide excision DNA repair pathway detects and repairs a range of such UV-induced DNA lesions. In bacteria, initial damage detection and verification is carried out by two proteins: UvrA and UvrB. Despite decades of study, the process of how these proteins locate damage remains unclear. Here we use high-speed interferometric scattering (iSCAT) microscopy, in combination with a surface-bound-DNA assay, to investigate early damage detection by UvrA. We have discovered that UvrA interacts with DNA in two phases; a slow phase (∼1.3 s-1) that correlates with an ATP-consuming state previously identified, and a second, much faster search mode. These faster interactions persist for ∼130 ms and using ATP analogues we determine this phase does not require ATP consumption. Including this new fast-search state in a model of the DNA search process reveals that only with this state is it possible for basal levels of UvrA to explore 99% of the E. coli genome within a single division cycle. Altogether, this work uncovers the presence of a rapid, energy efficient search mechanism, which allows UvrA alone to search the entirety of the E. coli genome within a single division cycle.