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.