Thank you for explaining the algorithm you were thinking of. It's a bit off ;-)

use File::Spec;

    my $mod_path;
    foreach my $i (@INC)
    {
        if ( -f File::Spec->catfile($i, 'Some/Module.pm') )
        {
            $mod_path = $i;
            last;
        }
    }
    if ($mod_path) {
        # Some::Module is installed here.
    } else {
        # Some::Module is not installed anywhere.
    }
[download]

The number of tests is directly proportional to the number of paths in @INC (that is, O(scalar @INC)), and is completely independant of the number of other modules that may be installed in any include path.