Lost Safari on my iPhone 5
Search for it with Spotlight — does it show up or not?

Reboot and check again. If it is still not showing up you can check if Safari is allowed in Settings → General → Restrictions → Safari.

In Spotlight, on the right of the icon and app name the Folder Name is displayed so you can find the location of the Safari icon.