[Solved]: Finding an element in a sorted array with at most three queries to larger elements

Problem Detail: 

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.)

However there is a constraint. Like in a game you have 3 lives. If you probe any element x > m in the array you will lose one life. You can probe as many elements you want which are smaller than m. If you find m, you win.

The solution to this should not be in linear time.

What I tried:

I will drop eggs from floors 1, 2, 4, 8.. And in log n time, I will find a sub-array in which m exists (at cost of 1 life). But this sub-array was of size at most n/2. I cannot repeatedly apply this process since, I have limited number of lives.

My thoughts

I am thinking that a solution does not exist to this problem which is faster than linear. How to prove this (if this is the case)? Can I create a contradiction from the assumption that a solution exists?

Asked By : Swapniel

Answered By : Lurr

If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$

If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $k + (k - 1)$ so total numbers of elements we can check is that way $n = k + (k-1) + (k-2) + ... + 1 = \frac{k(k+1)}{2}$ So if you have two lives you can find target element for ($k = \frac{1 + \sqrt{1 + 8n}}{2}$) $+1$ comparisons. It's $O(\sqrt n)$

So if we have three lives and $k + 2$ comparisons first we should check element of index $\frac{(k + 1)(k)}{2}$ than if we will lost life we will be able to check all earlier elements for $k + 1$ comparisons. So in full analogy $n = \frac{(k+1)(k)}{2} + \frac{(k)(k-1)}{2} + \frac{(k-1)(k-2)}{2} + \frac{(k-2)(k-3)}{2} +... + \frac{3\cdot2}{2} + \frac{2\cdot1}{2} = \frac{1}{6}(k+2)(k+1)(k)$

Therefore $n> \frac{1}{6}(k)^3$ and $k < \sqrt[3]{6n}$

So we can solve this for $O(\sqrt[3]{n})$

This is variation of quite known skyscraper and glass or crystal balls puzzle, though I may be didn't find correct name for it in English.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28910