2
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ @Monther yes, I've double check it and that's floor. $\endgroup$
    – LocalHosT
    Apr 15 at 21:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – plop
    Apr 15 at 21:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – plop
    Apr 15 at 21:23
  • 2
    $\begingroup$ @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. $\endgroup$ Apr 15 at 21:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – plop
    Apr 15 at 21:36
1
$\begingroup$

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

It is also true about the third task, with examples :
$A = [13, 49, 51, 52, 180]$
$B = [12, 48, 51, 52, 193]$

I hope my answer was helpful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.