Found out about this nice little tool which upgrades bash and zsh’s history searching.
You can optionally configure it by:
hh --show-configuration >> ~/.bashrc
It appears to add the above defaults to your bashrc without your consent. I installed it by adding the developers repository to apt-get as advised. It also apears to only have monochromatic or hicolor settings, I’d like it more if I could configure each colour option.