Until machines can read our minds (let alone humans) we'll have to rely on simple search suggestions. At Global Personals we had thousands of locations in our database, and we wanted users to be able to just type the location it was they were looking for, rather than having to search through a whole wad of places. I was responsible for conceptualising and designing the auto-suggest field to work for both Desktop and Mobile.
The functionality had to work on both mobile devices and desktop, so exploring the user interface happened simultaneously across both.
When it comes to designing an interaction with infinite possibilities there's one method in particular I like to use, and that's using Post-it notes. I find this method provides the quickest way for exploring and testing hundreds of minor interaction details that you'd otherwise miss with sketching.