The Android Market had this same problem in the early days. It was frustrating but pretty amusing how terrible Google, of all companies, was at getting search right in their app store.
The app named "Child Books" comes after coloring book, Nook, WebMD and many others. It's just that popularity matters MUCH much more than what you actually search for, and it takes days from the moment of getting popular (Google Maps style) to the moment when the algorithms start noticing.
A better way to search for an app called "child books" would be to use quotes around it.[1]
But I agree, Google Play's search can still be improved. Currently a search for GTA vice city [2] places the actual game in third place behind other related apps. These apps are The important thing to note is that both these apps have 100,000+ downloads while the game is <50,000 right now. So the number of downloads is given a higher weight than name (as it should be.) But the actual game should get a better rank than other things. As time goes on and more sites link to the game and more people download it, this will improve.
> Currently a search for GTA vice city [2] places the actual game in third place behind other related apps.
Looks like that's already changed in the last 3 hours. Now shows up in first place for me.
Third place is currently some ripoff scam app, which is another problem. (Is there any way to report clear ripoff/spam apps from the web storefront? Had to into Google Play to report "objectionable content", which was the closest I could find to a fraud report.)
Granted, but, seriously, Apple has never even feigned search-fu and MS/Bing has a better chance of making search even a competition.
On a side note, and this might titillate you; I am seeing serious cracks in Google's search skills as their other assets lack search or it is rather clunky. Now if Bing just didn't suck so bad, there might even be a challenger.
Same thing happened with Gmail back at the start. I guess it goes to show that web searches are a very specific kind of search, and just because Google is good at that doesn't mean it's good at anything else (relevance on the web is one obvious way it deviates from pretty much anything else you search)