patternMinor
Binary search uneven split number of queries?
Viewed 0 times
numbersearchsplitbinaryunevenqueries
Problem
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#110905, answer score: 3
Revisions (0)
No revisions yet.