@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 <[email protected]> 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 <[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%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 [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.
