I use Spotify on Android regularly and can only somewhat relate to what you're describing: when I know the artist, but not the song title and I have to literally search through his discography. But even that is doable in one click (see discography) from the artist main page (tried it just now, up to date app on Android 10) and playing the song is just tapping on it.

For regular use the search button is right in the middle on the bottom of the app and right next to it is the button to my library

Your criticism seems a bit harsh to me.