1
$\begingroup$

We are given an array $a$ of $n$ integers, such that the difference between each element $a[i]$ and the adjacent elements $a[i-1]$ and $a[i+1]$ is at most $1$.

Define a root of $a$ as an index $k$ in $1,\ldots,n$ such that $a[k]=0$.

If $a[1]<0$ and $a[n]>0$, then $a$ has at least one root. Moreover, it is possible to find a root using binary search, using $O(\log_2(n))$ operations.

In general, $a$ may have more than one root. MY QUESTION: What is the run-time of finding the smallest root (the smallest $k$ for which $a[k]=0$)? In particular: can it be done in time sub-linear in $n$?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

No, consider the array that:

  • 0 at a random index $a[i]$
  • 0 at index $n-1$
  • 1 at index $n$
  • -1 everywhere else

No sublinear algorithm can find the index $i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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