Are you sure you uninstalled them, or did you just remove the shortcut or widget from the homescreen. If you simply removed them from the homescreen, they're still there. Just tap the All Apps icon (the circular one with the 6 dots at the center of the bottom tray), and you'll see all of your apps.
It is unlikely that you uninstalled Google Search, because it's a system app. You can disable system apps, but can't uninstall them (assuming you haven't rooted your device).
You can always see a list of all apps you've ever installed from Google Play (even if you subsequently uninstalled them) by opening the Google Play Store app, tapping the My Apps icon (upper right, looks like a down arrow with a horizontal line at the bottom), and tapping "All" right next to "Installed" at the upper left.