I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average case.
However, I think, if such algorithms can exist, there are more than one of them.
Anyway, what I want to know if there is any known algorithm with restrictions given in title.
Note. It must be appliable to simple arrays without repeatitions (no precomputing/hashing).