How should I structure directory?

I am having trouble figuring out how I should structure a directory. The client already has a pre-existing wordpress site with theme. They would like to implement a search or look up tool. It needs to give the option of search based on zip code, city or name. The search results need to populate on a search results page. The search results will be Dr.’s Profiles including address, phone number, map, and image.

Is this something I can accomplish by tweaking the existing theme? If so how do I go about the multiple search options. Or is this definitely going to require a directory plugin of some kind?

Any recommendations would be incredibly helpful, thank you.