@Vaibhav: Your array doesn't work, because the problem statement says
that the array elements are distinct, but 2 is not distinct in your
array.
Elaborating on how to decide whether to look to the left or right, if
A[i] < i, look to the right, while if A[i] > i, look to the left.
Dave
On Nov 3, 8:29 am, vaibhav agrawal <agrvaib...@gmail.com> wrote:
> Hi Dave,
>
> How can we do a binary search on this array by using the function:
>
> Let f(i) = A[i] - i
>
> Please elaborate. I mean how can we take a decision whether to look into
> left or right.
>
> For example -> Pick array {1,2,2,4,5,6,8}
>
> Vaibhav
>
>
>
> On Wed, Nov 3, 2010 at 6:44 PM, Dave <dave_and_da...@juno.com> wrote:
> > @Lichenga2404: Assuming that the array is sorted into increasing
> > order:
> > If A[1] > 1 or A[n] < n, return false.
> > Let f(i) = A[i] - i. Do a binary search to find i such that f(i) = 0.
> > If such an i is found, return true; else return false.
>
> > Binary search is O(log n). It works because f(i) is an increasing
> > function, making it amenable to binary search.
>
> > Dave
>
> > On Nov 3, 2:54 am, lichenga2404 <lichenga2...@gmail.com> wrote:
> > > we are given a sorted array A[1...n] , composed of distinct integers,
> > > (the values can be negative). We want to determine if there is an
> > > index i such that A[i] = i.
>
> > > Give an O(logn) algorithm to solve this problem , and justify its
> > > correctness
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
