2
$\begingroup$

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).

$\endgroup$
5
$\begingroup$

Yup. Do interpolation search, but after $\log n$ iterations, if you haven't found the answer yet, switch to binary search. This ensures a $O(\log n)$ worst-case running time, while retaining the $O(\log \log n)$ average-case running time. Note that the average case only applies if you make a particular assumption about the distribution of values in the array.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh, right, how could I miss this trivial solution... $\endgroup$ – rus9384 Dec 7 '17 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.