Tags would be useful, if you were limited to two or three, to aid discovery. Search in the app stores seems to be pretty useless.
As opposed to putting "tags" in the app title (motivation for all calendar apps to be named something with Calendar) or X number of times in the description text (motivation for unnatural copy).
Disclaimer: Based on what little I know about search priority in Google Play.
On Amazon's non-app store, you can also buy search ads. Apple could implement something similar and take a larger cut of the paid install market. There are search ads on Google Play (see: http://adwords.blogspot.com/2015/07/launching-search-ads-on-...).