# Searching in sorted array with $O(\log n)$

Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows:

Suppose array $$A[1..n]$$ consist of $$n$$ distinct integers that is sorted in ascending order, then How many of below problems could be solved in $$O(\log n)$$?

and there were three statements;

• Find an $$i$$ index so that $$A[i]= i$$
• Find an $$i$$ index so that $$A \left \lfloor{i}\right \rfloor = 3i +2$$
• Find an $$i$$ index so that $$A[i]= 4i^{2} + 3i + 5$$

The answer sheet stated as one statement is true, Also there was no clue on which statement is true.

What is my issue?

So I think the first and second statements could be true, since the array is sorted then we can use Binary search with $$O(\log n)$$ to find the element with index $$i$$, also the first two statements are linear, thus I think that's what the question wants, If it's not then I don't know what the question exactly wants, any explanation would be handful.

• @Monther yes, I've double check it and that's floor. Apr 15 at 21:16
• @VladislavBezhentsev Note that they say that the values of the array are different. In the first problem the information that $A[i]>i$ (or $<i$) tells us that for all $j>i$ (or $j<i$) we must have $A[j]>j$ (or $<j$). This is what allows to look in the middle and either find the answer or discard half of the array.
– plop
Apr 15 at 21:16
• @LocalHosT The thing with the second (and third) problem is that the failure of an $A[i]$ to be equal to $3i+2$ can still allow for a solution in both $i-1$ and $i+1$. For example, if $A[i]$ takes any value $3i,3i+1,3i+3,3i+4$ one can still have $A[i-1]=3(i-1)+2=3i-1$ and/or $A[i+1]=3(i+1)+2=3i+5$. You can use an adversary argument. Assume that you have an algorithm that solves it in logarithmic time. Then, every time the algorithm checks a value, the adversary gives it one of those annoying values that don't give information about the rest of the array.
– plop
Apr 15 at 21:23
• @LocalHostT You can reformulate every statement in a form: "Find $0$ in the array $B[i] = A[i] - f(i)$", where $f(i)$ is $i$, $3i + 2$ and $i^2+3i+5$ correspondingly. Thus $B[i]$ is still monotonic in the first case and non-monotonic (and multimodal in general) in the second and third cases. Apr 15 at 21:28
• @VladislavBezhentsev A clarification on your comment is that in the second and third cases $A$ can be chosen such that $A[i]-f(i)$ is non-monotonic. In some case it can still be monotonic. The adversary needs to do some work to give a bad input.
– plop
Apr 15 at 21:36

You can answer the first question with binary search. Lets consider you're now discussing the interval $$[l, r]$$, and $$m = \frac{(l + r)}{2}$$. If $$A[m] = m$$, you have found an answer and you shall stop the search. If $$A[m] < m$$, then the answer must be in the interval $$[m + 1, r]$$, because if $$i \le m$$, then $$A[i] \le A[m] - (m - i) < m - (m - i) = i$$ (since the array is sorted in strictly ascending order and the elements are integers), thus no $$i \in [l, m]$$ can be the answer. Otherwise, if $$A[m] > m$$, then the answer must be in the interval $$[l, m - 1]$$, because if $$i \ge m$$, then $$A[i] \ge A[m] + (i - m) > m + (i - m) = i$$.

And I don't think you can solve the other tasks in $$O(lg(n))$$ using binary search. Consider these two examples :

$$A = [5, 6, 12, 14, 15]$$
$$B = [4, 9, 12, 14, 17]$$

As we know, binary search initially examines the middle element, in these cases, $$12$$. $$12 \ne 3 \times 3 + 2$$, thus the search has to continue. In both cases, decision must be the same, since the middle element is the same, therefore, if the algorithm decides to check the interval $$[4, 5]$$, the algorithm will respond NO to the array $$A$$, although $$5 = 3 \times 1 + 2$$, and if the algorithm decides to search the interval $$[1, 2]$$, it yields NO to the array $$B$$, while $$17 = 3 \times 5 + 2$$.

$$A = [13, 49, 51, 52, 180]$$
$$B = [12, 48, 51, 52, 193]$$