Finding the package which provides a given command

You can use command-not-found itself:

command-not-found --ignore-installed ls

will tell you which package contains the ls command. (--ignore-installed avoids taking into account installed packages, and in particular ensures that the command isn’t run immediately if it’s already installed.)

Alternatively, you can use apt-file:

apt-file search bin/ls

will list all packages containing a file whose path contains “bin/ls”. You can filter this to match only ls:

apt-file search bin/ls | grep bin/ls$

Yes, the command is command-not-found:

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

This has exactly the same functionality, because it is what the shell traps run to produce that output automatically already.

You can also use apt-file search firefox to find any matching files in a package.