Is it possible to see an ad for Tinder on lock screen if Tinder is not installed?
It's possible to get text messages from a service after deleting the app, but if the notification is branded like the app on the lock screen (with the logo), then the app is still on the device. It's not possible to get those kinds of notifications without the app being currently installed.

You can search for apps from the home screen by swiping down. That should allow you to search for the Tinder app by name, instead of browsing around for it.