You can use your package manager to find out which package `clang-tidy` provides. For example on Fedora/CentOS:
dnf whatprovides '*/clang*tidy*'
On Debian/Ubuntu you can use an analogous `apt-file search` command.
However, on Fedora 23 `clang-tidy` just isn't packaged. No match is found.
There is even an open bug report: Missing clang-query and clang-tidy
For Ubuntu/Debian, the LLVM project maintains an llvm apt repostiory. This should be the easiest way to get the latest `clang-tidy`. After configuring that repository and doing an `apt-file update` and `apt-file search` should return the package that provides `clang-tidy`.
An alternative to building from source is to use the upstream llvm pre-built binaries \- they are available for Fedora, CentOS etc. For example the one for Fedora 23 does contain clang-tidy:
clang+llvm-3.8.0-x86_64-fedora23/bin/clang-tidy