There aren't any algorithms to find things in an unsorted array in less than worst case linear time. I think you're confusing search (for some value) with select (a value with a given index in the sorted array).
If you want to do several searches on the same data - that is initially unsorted - you can get better than O(n) per query. But like you said - not for the first one.
