Pick any app you want and search for it. Ideally it has a pretty unique name and not just a dictionary wod. What will you see? The first result will always be an ad for a completely different app.
Google has long dealt with this problem with AdWords and search results. Google still tries to make the exact thing your searching for be the #1 organic result. Yes there are promoted links but they're not as prominent.
The App Store #1 result, which is always an ad, is quite literally half the screen.
I don't know how advertising works on the App STore but I suspect it's a CPM model not a CPC model (like AdWords). So Apple just doesn't care. But I don't think this would ever have happpened in the Steve Jobs era.