0
$\begingroup$

Given sorted array $A[1..n]$, we want to find an element such that, $A[i]=i^2$,Can we use binary search to find such a element?

My Attempt: initially, I read this link, but I can't understand the comments for why we can't find that element in $O(\log n)$. Any hint be appreciated.

$\endgroup$
1
$\begingroup$

No. Let's define an array $B$ as $B[i] = i^2 - 1$. Clearly it has no solution, but it is sorted.

Now I define $A$ to be a copy of $B$, with exactly one element, $A[k]$ incremented by one. This array is still easily seen to be sorted, but there's no way to find out which $k$ I used to increment a single element other than scanning the complete array. After all, if you inspect $n - 1$ indices of this array, I could've chosen $k$ as the single index you didn't look at.

$\endgroup$

Your Answer

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