I have a question for a data structures assignment.
You are given a sorted array of integers. Your goal is to find if there is an index 1<= k <= n so the A[k] = k
My solution...
Input: A[1...n]
Output: True/false
IndexMatch(A)
match <--- false
end <---false
l <--- 1
r <---n
k <--- celiling(n/2)
while match = false and end = false
if k < A[k]
if k = l + 1, then k <--- l
else r <--- k , k <--- l + floor( [r - l -1]/2 )
else if K > A[k]
if k = r - 1, then k <--- r
else l <--- k, k <--- l + floor( [r - l -1]/2 )
else if K != A[k] and ( k = l or k = r )
end <--- true
else
match <--- true
return(match)
I know the easy, although not the most efficient, way to solve this problem would be to iterate through the array and compare the index to the value found at that index. I want to say that in worst case, a solution such as the one mentioned would have a running time of O(n)?
Is my solution any better? We briefly (and vaguely) touched on analyzing algorithms in class and I am a little weary about analyzing my own algorithms.
