@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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
