[__david__]

I prefer "apt-file search" which is much faster than "dpkg -S" at the cost of some disk space and having to periodically do "apt-file update".

[ars]

apt-file search is [also] for uninstalled packages. If all you care about are packages actually installed use dlocate