These things are not mutually exclusive, right? I use both to great effect.
Were you thinking of autosuggestions? (completions are command-specific assistance you get when you hit Tab)
Have you tried fish? You can partially complete the query and use the arrow buttons, and the search is fuzzy if you use the previous commands search. Typing Sudo for instance and arrow will show my previous sudod commands.
Yup, its great. Problem is, the syntax is slightly different from Bash. So whenever I use a shell script or use some kind of commands where the differences are incompatible, I tend to switch to Bash. And then my history doesn't add up with the one from Fish.
For fuzzy search I bound ctrl+r to fzf (you can use Rust's sk too).