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 <[email protected]> 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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
