The Firefox bookmark sidebar has a search box at the top. I tend to save bookmarks to a big bucket and then search for them. It is smaller search space than full web or browser history.