0
$\begingroup$

Given sorted array $A[1..n]$. We want to find an element such that $A[i]=3i+2$ in $O(\log n)$(binary search).

I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, but i can't use that technique to solve mentioned problem. Any hint be appreciated.

$\endgroup$
3
  • $\begingroup$ Which algorithms do you know that work for sorted arrays in $O(\log n)$ time? $\endgroup$
    – Pål GD
    Mar 17, 2021 at 19:31
  • $\begingroup$ Binary search.. $\endgroup$
    – user132812
    Mar 17, 2021 at 19:31
  • 1
    $\begingroup$ Did it not work? $\endgroup$
    – Pål GD
    Mar 17, 2021 at 19:47

1 Answer 1

0
$\begingroup$

Define $B[i] = (A[i]-2)/3$. Now you want to find an index $i$ such that $B[i] = i$.

$\endgroup$
5
  • $\begingroup$ Runtime will be $O(n)$? becuase we must read each $A[i]$ $\endgroup$
    – user132812
    Mar 17, 2021 at 20:51
  • $\begingroup$ You say that you knew how to solve the problem of finding $i$ such that $A[i] = i$. This appears to be identical to your problem (unless you assumed more about $A$). $\endgroup$ Mar 17, 2021 at 20:53
  • $\begingroup$ Yes i know, but the problem is, for calculate each $B[i]$ we need $O(n)$ time. But i say we must do it in $O(\log n)$. $\endgroup$
    – user132812
    Mar 17, 2021 at 20:55
  • $\begingroup$ You don't need to calculate all of $B$. Whenever the algorithm queries $B[i]$, you answer with $(A[i]-2)/3$. $\endgroup$ Mar 17, 2021 at 20:56
  • $\begingroup$ Thanks. it's amazing answer. $\endgroup$
    – user132812
    Mar 17, 2021 at 21:03

Your Answer

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