Thanks Dave for the clarification. It works!!!! On Wed, Nov 3, 2010 at 7:20 PM, Dave <[email protected]> wrote:
> @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%[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]<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.
