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