efficient algorithms with array of increasing integers

Question

I've been self teaching myself data structures in python and don't know if I'm overthinking (or underthinking!) the following question:

• My goal is come up with an efficient algorithm

• With the algorithm, my goal is to determine whether an integer i exists such that A[i] = i in an array of increasing integers

• I then want to find the the running time in big-O notation as a function of n the length of A?

so wouldn't this just be a slightly modified version of O(log n) with a function equivalent to: f(i) = A[i] - i. Am I reading this problem wrong? Any help would be greatly appreciated!

Answer 1

Note 1: because you say the integers are increasing, you have ruled out that there are duplicates in the array (otherwise you would say monotonically increasing). So a quick check that would rule out whether there is no solution is if the first element is larger than 1. In other words, for there to be any chance of a solution, first element has to be <= 1.

Note 2: similar to Note 1, if last element is < length of array, then there is no solution.

In general, I think the best you can do is binary search. You trap it between low and high indices, and then check the middle index between low and high. If array[middle] equals middle, return yes. If it is less than middle, then set left to middle+1. Otherwise, set right to middle - 1. If left becomes > right, return no.

Running time is O( log n ).

Edit: algorithm does NOT work if you allow monotonically increasing. Exercise: explain why. :-)