Fastest way to search for an element in unsorted array

You're right, the fastest way is to simply iterate through the array and look for it. Without further information, there is nothing better you can do.

Unless you have a quantum computer, that is.

Make it parallel. Divide the array in chunks and search in parallel. The complexity will be O(n) but running time will be much less. Actually it will be proportional to no. of processors you have.

You can use Parallel Patterns Library in C++