Easy question: How do I search for apps on my S3?
Press and hold the menu button (button to the left of the physical home button). It will launch google now and if you enter the first letter of the name of an app it should start listing those apps, at least it does it on my galaxy s3.