Craft and lat/long search
Yes, Craft would be a great solution for that!

For the proximity search feature, check out the Smart Map plugin. (Disclaimer: I'm the author.) It allows you to input addresses for each location, then your users can conduct a search to find the closest locations.