You could search for packages with
apt-cache, searching for a pattern is like
apt-cache search <pattern>
If you only want to search in package names
apt-cache --names-only search <pattern>
Pattern are regular expressions, but be aware to protect them from shell expansion. If you use more than one pattern, they are and'ed together.
The output is the short description, if you want a long one, use the
aptitude can do more specific searches, for example something like
aptitude search '?installed?not(?automatic)?priority("optional")?name("^s")'
aptitude is not installed by default.