No that is right, emacs has two main contenders for "fuzzy search" - ido-mode and helm. They act as completion engines for all kinds of search; file, word, buffer, commands etc.
Helm acts similar to Ctrl+P, ido is like an incremental search so finding a file named BasketViewController.swift in path ~/Code/MyApp/;
In helm would be 'bvc', whereas in ido it would be c -> code (hit enter), m -> MyApp (tab across if its not first result, enter) Bas -> BasketViewController.swift
The closest vim has (to my knowledge) is Unite/Denite, although fzf is functionally similar minus a couple limitations on starting new fzf searches from the callback of another.
Like helm, fzf and Unite can be fed arbitrary completion candidates, custom callbacks, mostly customized fuzzy matching. fzf is very fast, which is the main claim over what seems to be the more featureful Unite/Denite.
Does FZF work with a list of vim's ex commands as source (preferably including plugin defined commands)?
That functionality (helm-M-x) has been the best part of using emacs. It's always something I miss when I'm back in vim land. Really nice to just be able to discover these things without a mess of gui everywhere distracting me when I don't need it.
It's magic because everything is a single lisp environment. So the client/server thing vim does isn't as unified.