Does Homebrew have a command-not-found hook? Arch Linux's pkgfile has a command-not-found hook that you can source from your shell's startup file (.zshrc, .bashrc, or whatever).  Does Homebrew have anything roughly equivalent to this?
Have a look at homebrew-command-not-found. The project tries to reproduce Ubuntu’s command-not-found for Homebrew users on OS X.