The command to search for packages is apt-cache search, not apt-file. It does not need root permission to run, unlike apt-get. According to the instructions of the page you gave, auto-apt search would work for this utility.
You probably want to read about the possibilities and limitations of auto-apt first, which will attempt to take care of dependency issues automatically. The following instructions are for fulfilling dependencies manually:
To prepare, install the package apt-file, and then run sudo apt-file update.
so thats why it was not found, needed to install first apt-file.