OK , I see . Thank you Dave
2010/11/3 Dave <dave_and_da...@juno.com>
> @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>
> <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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
licheng
--
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.
