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
    How does interpolation search work ? – Suresh Venkat Oct 15 '10 at 5:45
  • @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. – Sylvain Peyronnet Oct 15 '10 at 10:55
  • 1
    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. – Tsuyoshi Ito Oct 15 '10 at 20:36
  • 2
    @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. – Daniel Apon Oct 16 '10 at 2:32
  • 1
    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. – Tsuyoshi Ito Oct 17 '10 at 21:26
up vote 4 down vote accepted

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

  • Thanks! Exactly the type of results that I was expecting to have been done. I will try to download the papers from the university. – Jeremy Feb 25 '11 at 15:19
  • 1
    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. – jbapple Mar 23 '11 at 5:52

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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