Find an element in array where each element is one more or one less than its preceding element

Question

Given an array , each element is one more or one less than its preceding element .find an element in it.(better than O(n) approach)

I have a solution for this but I have no way to tell formally if it is the correct solution:

Let us assume we have to find n.

• From the given index, find the distance to n; d = |a[0] - n|
• The desired element will be atleast d elements apart and jump d elements
• repeat above till d = 0

Answer 1

Yes, your approach will work.

If you can only increase / decrease by one at each following index, there's no way a value at an index closer than d could be a distance d from the current value. So there's no way you can skip over the target value. And, unless the value is found, the distance will always be greater than 0, thus you'll keep moving right. Thus, if the value exists, you'll find it.

No, you can't do better than O(n) in the worst case.

Consider an array 1,2,1,2,1,2,1,2,1,2,1,2 and you're looking for 0. Any of the 2's can be changed to a 0 without having to change any of the other values, thus we have to look at all the 2's and there are n/2 = O(n) 2's.