Descobrir qual pacote de repositório fornece um comando

Question

Quando o pacote command-not-found é instalado, um pacote é sugerido se um comando é invocado e não está instalado, por exemplo

$ convert
The program 'convert' is currently not installed.  To run 'convert' please ask your administrator to install the package 'imagemagick'
convert: command not found

Se command-not-found não estiver instalado, há um comando apt que posso invocar para descobrir qual pacote fornece um binário específico? Nesse caso, o comando apt-cache search é muito inespecífico.