Laser ultrasonic scanning, especially full-field wave propagation imaging, is attractive for damage detection due to its noncontact nature, sensitivity to local damage, and high spatial resolution. However, its practicality is limited because scanning at a high spatial resolution demands a prohibitively long scanning time. Inspired by binary search, an accelerated laser scanning technique is developed to localize and visualize damage with reduced scanning points and scanning time. The distance between the excitation point and the sensing point during scanning is fixed in this technique to maintain a high signal-to-noise ratio for measured ultrasonic responses. First, the approximate damage boundary is identified by examining the interactions between the ultrasonic waves and damage at the sparse scanning points that are selected by the binary search algorithm. Here, a time-domain laser ultrasonic response is transformed into a spatial ultrasonic domain using a basis pursuit approach so that the interactions between the ultrasonic waves and damage, such as reflections and transmissions, can be better identified in the spatial ultrasonic domain. Then, the region inside the identified damage boundary is visualized as damage. The performance of the proposed accelerated laser scanning technique is validated through the experiment performed on an aluminum plate with a crack. The number of scanning points that is necessary for damage localization and visualization is dramatically reduced from N.M to 4log(2)N.log(2)M even for the worst case scenario. N and M represent the number of equally spaced scanning points in the x and y directions, respectively, which are required to obtain full-field wave propagation images of the target inspection region.