If you have a smartphone with Windows Phone 8.1 and have tried to search for apps in the Windows Phone Store without success, you are not alone. The search feature appears to be down for at least some users of the OS.
We have also tried and failed to bring up apps via the search feature in the Windows Phone Store. However, this does not affect the Featured apps catagory. This issue doesn't appear to affect Windows 10 Mobile devices. We will update this post when the search problems have been resolved.
Thanks to everyone for the tips!