Another great tool, built on top of nix-locate, is comma. So for any program foo, if you have foo installed, you can run it like this:

  foo

And if you don't have it installed, you can run it (without installing!) like this:

  , foo

And if multiple different packages provide a program named bin/foo then comma lets you interactively choose the one you want, and remembers your choice so you don't have to specify again unless you choose to via the -d flag.