The problem lies in the sole definition of the word "installed". There are several ways to interpret it.
A typical and most proper way to "install" a program is to use a package manager tool(s). These vary from distribution to distribution: on Gentoo, there is
emerge and and a bunch of other helpful programs around portage; on Debian-based systems (like Ubuntu), there are
apt-<something> tools and so on. These tools are what you should use whenever possible - both for installation and searching for available/installed software - their main job on the system is to maintain all the information about your official software.
Software that is not available in the repositories can also be installed by its own specific installation scripts. Such software will not be automatically seen by the system management tools - which can cause various problems. To find components of such programs, you are left to use tools like
You can also build a program, place it "by hand" and adjust your environment (like
PATH) so that it becomes usable. From both the user's and the system's point of view it can be much different, slightly different or not different at all compared to the previous approach.
In your case, you should distinguish between finding a binary and determining if a certain package is installed. For the practical part of finding a binary, you can just use
whereis. Note that the
PATH environmental variable can be different for root and non-root users. If you want to determine if a package is installed (using the first interpretation of that word), use your distribution's package management software.