The edge-detection method based on polynomial annihilation that was recently proposed has been applied to locate small damage in structures and demonstrated its effectiveness on beam-like structures. However, significant computational effort involved in this method lengthens the damage detection process, which forbids real-time damage detection. To alleviate this difficulty, in this article, we improve the method suggested by Surace and colleagues by first using the divided difference approach on the identified mode shapes to identify the regions in which jump discontinuities are potentially located and then only applying the polynomial annihilation derivative detector to data points in the identified regions. In this way, the computational burden of this approach is significantly relieved, while the accuracy of damage location is still maintained. The improved method has been validated by numerical simulations on a complex cable-stayed bridge model. This approach does not require baseline response data of structures.