Do you have access to any material? If so, there's the Urban bounty hunter background in SCAG. As for classes:
- Ranger beast master, Mastiff companion, human favored enemy
- Rogue Inquisitive with expertise in Perception, Insight and Investigation
- Diviner Wizard with all the scrying, locate and commune spells.
- GOO warlock with all the sight-based invocations + divination and mind-reading spells.
Of course you can mix all of the above.
Good calls. I completely missed the SCAG background. The Ear to the Ground feature works very well to find those in urban environments.
UA Ranger has some of the needed skills. Their sense ability is hit or miss - useless in an urban environment but useful for finding the person in the middle of the forest, or the people kidnapped by hobgoblins, it works fantastic. The Mastiff is on-point. Probably the best mundane choice in wilderness.
That could multiclass well with the Rogue Inquisitive if it had oomph. But they don't really get a lot of support until 9th. Sure, they don't fail horribly to make sure you aren't lying at 3rd, but it's not until 9th that the ability to take advantage on perception/investigation. But as a skill monkey they are well suited for it.
Diviner I really want to work, especially how well a high INT will pair with an Investigation roll, but what spells actually help you find someone? Locate creature requires you to be familiar with he target ahead of time. Sure Charm Person or Suggestion could help interrogate accomplices but those aren't divination spells. Contact other Plane at 5th is a long way to wait.
Cleric, with spells like Augury and Speak with Dead actually seems to be the better caster. Are there any domains that really work for a bloodhound type of character?
Bards can do expertise and also getting information out of people well, plus spells like Speak with Animals and whatever they poach with magical secrets. Combined with your suggestion of the Urban Bounty Hunter background and they'd be a force to be reckoned with in any city environment, plus casting.
If there was more mechanical synergy between UA ranger and bard that would work out well to cover everything. Not that it's bad, just disparate - outside the tracking skills they don't reach enhance each other like just staying in one class would.