You can design just one search bar that caters for both, exactly like Google Maps does.
- The critical key component is to have auto-suggestions immediately pop up as you type which makes it easier for the user to find what he/she is looking for.
- The other important part is to make sure the data groups are presented consistently for example in the attached: City, Region, Country.
- Lastly, you should highlight the term they are typing to make it easy for the user to spot in the list of suggestions.
In the example attached via searching for "New York" on Google Maps I have the ability to quickly get to either data group I am looking for.
Based on your example of thinking about your data as countries and cities this would work.
What do you think?
To elaborate and show the usage of the example above you can also look at how Quora and Facebook handle this. Again in both examples I was searching for "New York"
Grooveshark:
Here is an interesting way - still using suggestions - but separating the groups of data in a table structure within the suggestions.
Quora:
Facebook: