Gfilui

I would like to search for which package provides an uninstalled command.

apt-cache search keyword

is good, but the search keyword can be all or part of a package name or any words used in its description, not necessary the name of a program/command.

Is there a better way?

For example, I can't tell which package contains the program xlock:

$ apt-cache search xlock
away - Terminal locking program
devrplay3 - rplay network audio system - basic library
librplay-perl - rplay network audio system - perl modules
librplay3 - rplay network audio system - shared libraries
librplay3-dev - rplay network audio system - development libraries
rplay-client - rplay network audio system - basic clients
rplay-contrib - rplay network audio system - contributed binaries
rplay-server - rplay network audio system - server
xautolock - Program launcher for idle X sessions

Thanks.

Install apt-file

sudo apt install apt-file

Perform an initial update of its database

sudo apt-file update

Then (for example)

$ apt-file search 'bin/xclock'
x11-apps: /usr/bin/xclock

See also How do I find the package that provides a file?

Normally on default installs of Ubuntu, when you type an uninstalled command in the terminal you should get a list of packages that provide it, or else a list of similarly-named commands if that specific command wasn't found; it seems that xlock is simply no longer provided in the main Ubuntu repositories. It was available for 12.04 (http://manpages.ubuntu.com/manpages/precise/en/man1/xlock.1.html), but no longer.

For xlock:

$ xlock
No command 'xlock' found, did you mean:
 Command 'mlock' from package 'mlock' (universe)
 Command 'xclock' from package 'x11-apps' (main)
 Command 'vlock' from package 'vlock' (universe)
 Command 'lxlock' from package 'lxlock' (universe)
 Command 'wlock' from package 'sendfile' (universe)
 Command 'slock' from package 'suckless-tools' (universe)
 Command 'rlock' from package 'ruby-lockfile' (universe)
 Command 'flock' from package 'util-linux' (main)
 Command 'clock' from package 'xview-clients' (universe)

Example for one not installed but available:

$ rlock
The program 'rlock' is currently not installed. You can install it by typing:
sudo apt install ruby-lockfile

Go to packages.ubuntu.com and scroll down to "Search the contents of packages". Enter the program name in the box and click Search. A list of packages containing files named that will be displayed, without you having to install apt-file.

In this case, just like the other suggestions here, it will display nothing useful. That's because xlock came from the xlockmore package, xlockmore doesn't seem to have been shipped in Ubuntu since precise (released in 2012), and packages.ubuntu.com only has information for supported releases, currently back to trusty (released 2014).