Best practice to help users search for records efficiently

A user needs a powerful search functionality to find a specific record, or group of records among years of information stored in the system. What is the best approach for this scenario?

The current pain-point that my users face is that looking for a record takes time, and they are having to enter the from and to dates every time, for accuracy.