I have been having trouble with the search option showing up on my Samsung Galaxy S3. Nothing triggers the absence of the search bar - it just isn't there. I am using Version 220.127.116.117 and I am in the US. I am also a premium user, don't know if that matters.
So I got a new phone running Android 5.1 and I no longer have an issue with the Search not appearing. Based on that and this thread, I'm guessing it's an issue specifically with Android versions under 5. I saw an update was released today, but there's no mention of this bug being fixed. I'm also receiving notifications of a "solution", but it is just a poor work-around. Hopefully Spotify can get this fixed quickly, since the only real fix so far has been to upgrade to a newer phone running Android 5 or better.
Well, they did an upgrade about an hour ago, my tablet told me at the time. I only allow upgrades when connected to wifi (otherwise my meager data allowance gets completely eaten) so it may have been released some time earlier.
I got search each time I looked, without having to shut down tablet & restart. Hope this holds.
There are other things still screwed, like not always getting an album list when you search by artist, but that's minor when compared to no search at all.
I just had the same problem but i figured it out like in 5 min so for everyone that struggles the only thing you have to know is that theres some kind of glitch in the app and the search did not dissappear it is only covered by the 3 lines and just above the Browse line what you have to do is try and click that little space between the grey and the black. At least this worked for me.