How to find where a library is installed?

Probably the issue with the locate command is that the database has not yet been updated to reflect the newly-installed package files. You could force an update (sudo updatedb) or use the find command instead, but probably the easiest solution on systems like Ubuntu that use the dpkg package management tools is to list the package contents

dpkg -L libgoogle-perftools-dev

or to check for the profiler.h file location specifically

dpkg -L libgoogle-perftools-dev | grep 'profiler.h'

Usually, pkg-config helps in most of these cases pkg-config --list-all lists packages that are "known" to your system. And then pkg-config --libs --cflags <package> is good enough to provide linker and include information.