A sorted array A[1...n] composed of distinct integers
=> A[i] < A[i+1] for i = 1..n-1
=> A[i]-i < A[i+1]-i for i = 1..n-1
=> A[i]-i <= A[i+1]-(i+1) for i = 1..n-1
Let B[i]=A[i]-i for i=1..n, then B[1..n] is sorted in non-decrease
order. A[i]=i <=> B[i]=0.
Do a binary search for 0 in B[1..n] is sufficient to solve the problem.
On 2010-11-3 15:54, lichenga2404 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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
