finding an index i such that a[i] = i [duplicate]

This question already has answers here: Closed 11 years ago. 开发者_StackOverflow社区

Possible Duplicate:

Interview question - Search in sorted array X for index i such that X[i] = i

You are given with a sorted array of integer and the length of array. Now you have to find an index i such that a(i)=i. I am able to do it in o(logn) if index is given but what about if index i is not mentioned?

---

As Alexandre stated in a comment, the foreknowledge of the index means it's O(1), not O(log N).

And, unless there's some information you're not telling us, you need O(n) time to do this without that foreknowledge:

for x = 0 to len(a) - 1:
    if a[x] = x:
        return x

---

Clarification: The original question did not state that the list was sorted, that was added later. Since that makes the question a duplicate of this one, you should look to the answers there for the solution.

This answer will be left as is since there's no point in duplicating the others, and it's relevant for the unsorted case.

---

With the information given, you need to check values until you find a match. The worst case scenario (no match, or match found in last cell) is O(n). If the array is already sorted you can do a binary search, which is O(log n).

Your claim is either false, or you left out some information.