As you already pointed out, you're not describing a problem, but rather a family of related problems. Each of which has a solution that best fits.

Traversing an array should never be used for searching

This really hits me, in particular the never. If your search needs are rare, for example, or you don't have particular needs in term of efficiency - why not? Keeping it simple seems the most winning solution to me, human cycles are quite more expensive than CPU ones. And List::Util contains tools that are there only to be put directly into production code (yes, it's part of the CORE MODULES).

More or less, I'd use a hash when I know in advance that I'll do a lot of lookups. Building the hash from the array has its cost, both in term of space and time (yes, you have to traverse the whole array!), so I'd keep this solution for occasions where I really need it.

Last, but not least, your request for code is funny. Why not posting an initial implementation? The description seems already near to Perl code, and it would have probably helped you better than a look for cut-and-paste.