# Search for specific element in sorted array

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.

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

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

• Runtime will be $O(n)$? becuase we must read each $A[i]$
– user132812
Mar 17, 2021 at 20:51
• 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$). Mar 17, 2021 at 20:53
• 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)$.
– user132812
Mar 17, 2021 at 20:55
• You don't need to calculate all of $B$. Whenever the algorithm queries $B[i]$, you answer with $(A[i]-2)/3$. Mar 17, 2021 at 20:56