An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such that the height of the tree is $\lceil \log{_{2-\epsilon}n}\rceil$, where $\epsilon=\frac{2}{9}$.
If we had to make a perfectly balanced binary search tree, we need to choose the median of the $n$ elements as root in every recursive call. But the height is not exactly $\lceil \log{_{2}n}\rceil$; there is a relaxation by $\epsilon$. So instead of choosing the median we need to choose any value (randomly) from the middle $x\%$ of the sorted version of $\mathcal{A}$. For example, suppose$\mathcal{A}=\{4,2,3,6,1,5,7,10,9,8\}$, $\therefore\mathcal{A_{sorted}}=\{1,2,3,4,5,6,7,8,9,10\}$. Now because the height is not exactly $\lceil\lg n\rceil$, so instead of choosing the median, we need to choose one element randomly from the middle $30\%$ of the elements (say for example), $i.e$ one element randomly from $\{4,5,6\}$. Here this value $30\%(x\%)$ will depend on $\epsilon\ (\frac{2}{9})$. My question is how to derive this $x\%$ from the height information given $i.e$ $\lceil\log{_{2-\epsilon}n}\rceil$ ? $$\lceil\log{_{2-\epsilon}n}\rceil = \left\lceil\frac{\log{_{2}n}}{\log{_{2}{(2-\epsilon)}}}\right\rceil=\left\lceil\frac{\log{_{2}n}}{0.83}\right\rceil$$
I don't need a full explanation, any hint would suffice.
