For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/2, then number of queries is log with base 3/2. Why is this so? Would someone please help me get an intuitive understanding of why this works?
1
-
3$\begingroup$ Hint: You have to consider the worst case, so a 1/3 2/3 split that would always leads to "what you search is in the 2/3 side". $\endgroup$– OptidadCommented Jun 19, 2019 at 15:21
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The number of queries in the question is assumed to mean the exact upper bound of the number of queries in the worst case. So, only the worst case is considered except in exercise 3. That is, the wanted element will be in the "2/3" part after each query.
Suppose we have $3m$ ordered items currently. After a split by ratio 1/3:2/3, we will be left with $2m$ choices. So each query reduces the number of choices by a ratio of $3m:2m=3:2$.
After $k$ queries, the number of choices will be reduced by a ratio of $(3/2)^k$. In order to have only one choice left after $k$ queries, we should have $\frac{n}{(3/2)^k}\approx 1$, where $n$ is the number of original items. So the number of queries, $k$ is about $\log_{3/2}n$. That is the simple intuition.
Of course, the above reasoning is not rigorous since we could have $3m+1$ ordered items. The number of items left after one query will be $2m$ or $2m+1$ (depending on how we round the fractional item), which is approximately $(2/3)(3m+1)$.
Or we could have $3m+2$ ordered items. The number of items left after one query will be $2m+1$ or $2m+2$, which is still approximately $(2/3)(3m+2)$.
It turns out that the number of queries will be between $-3+\log_{3/2}n$ and $1+\log_{3/2}n$ for all $n>1$. So there is not much error to say the number of queries is log of $n$ with base 3/2.
Exercise 1. How many queries are needed if we binary search 26 items with splitting ratio $1/3:2/3$? ( Answer: 6 for floor, 7 for rounding or 8 for ceiling.)
Exercise 2. Write the approximate formula for the number of queries needed if we binary search $n$ items with splitting ratio $1:t$.
Exercise 3. Write the approximate formula for the number of queries needed in the best case if we binary search $n$ items with splitting ratio $1/3:2/3$.
-
$\begingroup$ I actually have a doubt, shouldn't it be n divided by (3/2)^k is approximately equal to 1 in the second para? $\endgroup$– HemaCommented Jun 20, 2019 at 4:22
$\begingroup$
$\endgroup$
1
On a side note, the complexity still remains in the order of Log. This is very well discussed in Brian Dean's paper on Randomized Reduction Lemma. https://dl.acm.org/citation.cfm?id=2677251
-
1$\begingroup$ We prefer to keep our posts self-contained, maybe you could summarize relevant parts? $\endgroup$– EvilCommented Jun 25, 2019 at 1:08