Analyzing Algorithms

[restin84]

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.

Edited February 18, 2012 by restin84