Consider the following two algorithms for searching in a sorted array of $n$ elements:

A) interpolation search and binary search simulated in parallel, and

B) search through alternating interpolation steps and binary steps.

Both algorithms are of worst case complexity $2\lg n+1$ (and average complexity $2\lg\lg n$ for a reasonable distribution). Is there a complexity model which permits to separate those two algorithm (expressing when one is better than the other)? In particular, is there an example where the simulation in parallel is outperforming the mixed search algorithm?

---Some Basic Background---

1) Interpolation for element $x$ in a sorted array $T$ between position $i$ and $j$ makes a comparison at position $g=i+(j-i)/(T[j]-T[i])*(x-T[i])$, and reduces the search interval to $[i,g]$ or $]g,j]$ according to the result (as opposed to binary search, which compares $x$ to the element at position $(i+j)/2$.)

2) The worst case complexity of the search algorithm simulating in parallel binary search and interpolation search is $2\lg n+1$: Given two algorithms $A$ and $B$ of worst case complexities $f(n)$ and $g(n)$, the worst case of the parallel simulation of $A$ and $B$, stopping as soon as one terminates, has complexity $2\min\{f(n),g(n)\}\in O(\min{f(n),g(n)})$. The complexity of the search alternating steps from binary search and interpolation search is $2\lg n+1$ as well, because the search interval is at least reduced by two every two comparison.

  • 1
    $\begingroup$ How does interpolation search work ? $\endgroup$ Oct 15, 2010 at 5:45
  • $\begingroup$ @Suresh The idea is to estimate the next position to be checked in a sorted array based on a linear interpolation of the search key and the extremal values of the search interval. $\endgroup$ Oct 15, 2010 at 10:55
  • 1
    $\begingroup$ If I am not mistaken, the point of running two different algorithms in parallel (or interleaving two algorithms) is that the worst-case time becomes the faster of the worst-case times of the two algorithms. $\endgroup$ Oct 15, 2010 at 20:36
  • 2
    $\begingroup$ @Tsuyoshi, you're correct. I think the question is (really) asking about non-worst-case analysis -- for example, average case runtime or expected runtime over certain distributions over the search keys. Basically, any type of "finer grade" analysis than optimizing only for the worst case. $\endgroup$ Oct 16, 2010 at 2:32
  • 1
    $\begingroup$ Voted to close. As I wrote in a comment, I cannot understand the question in its current form, and I believe that it is not my fault. $\endgroup$ Oct 17, 2010 at 21:26

1 Answer 1


In Willard's Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time, he references a preliminary version (of the linked paper) entitled "Surprisingly efficient search algorithms for nonuniformly generated files" appearing at the 21st Allerton Conference on Communication Control and Computing in 1983, pp. 656-662. I can't find this paper on the web, but in the later (linked) version above, he says that the older paper shows that the synergy between binary and interpolation search can reduce search time to $o(\log n)$ for certain non-uniform distributions of record keys.

Specifically, call a PDF $\mu$ regular if there are $b_1, b_2, b_3, b_4$ such that $\mu(x) = 0$ for $x < b_1$ or $x > b_2$ and $\mu(x) \geq b_3 > 0$ and $|\mu\prime(x)| < b_4$ for $b_1 \leq x \leq b_2$. For data produced by regular PDFs, interpolation search takes $\Omega(\log n)$ expected time, while binary search takes $\Theta(\log n)$ expected time. Interleaving them, however, takes $O(\sqrt{\log n})$ expected time.

You may also be interested in Willard and Reif's "Parallel processing can be harmful: The unusual behavior of interpolation search", which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".

  • $\begingroup$ Thanks! Exactly the type of results that I was expecting to have been done. I will try to download the papers from the university. $\endgroup$
    – J..y B..y
    Feb 25, 2011 at 15:19
  • 1
    $\begingroup$ I tried to get the paper from the Allerton Conference, but I can't even find it in a library, except at ETH-Bibliothek Zurich, which is very far from where I live. I emailed the author, but I have yet to hear back. Please let me know if you find the paper anywhere. $\endgroup$
    – jbapple
    Mar 23, 2011 at 5:52

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.