fzf by Junegunn Choi is a ctrlp.vim-inspired Ruby script that allows you to find shell commands with a fuzzy finder. If you use tmux then it can be launched in a split window.
It comes with keyboard shortcuts for bash, zsh, and fish, and there is Vi-mode compatibility support for bash.
You can also use it with Vim, which means you can use the same fuzzy finder everywhere. It doesn't block Vim while it searches, so you can keep typing while it works. For documentation on Vim options, see the readme on GitHub.