What kind of search algorithm could you use to solve this problem?

Question

Given an array of n integers A[0…n−1], such that ∀i,0≤i<n, we have that |A[i]−A[i+1]|≤1, and given x=A[0], y=A[n−1], we have that x<y. Locate, in O(log n), any index j such that A[j]=z, for a given value of z, x≤ z ≤y.

As I see it, the problem restricts that the -difference or "distance"- between the elements that are adjacent to each other is at most 1, but as I understand it, that does not mean that the array is ordered, it is true that there are sub-sequences, of any size, which can follow an ascending or descending order but precisely for this reason I do not see a clear way to use an algorithm that can search for the index in O(log n).

I was thinking of examples that would meet the constraints:

[1,2,1,2]

[-1,0,1,2,2,1,0,1,2,3]

[4,5,6,7,8,9,10,11,12,13,14,13,12,11,10]

[4,3,2,1,0,1,2,3,4,5]

I really don't know if I'm understanding the problem correctly :C.Could someone give me a hint please?

Answer 1

Even though the array is not sorted, you can solve it similarly to binary search, by checking in the middle (let it be m), and then:

1. If z == m - you are done.
2. If z < m - divide and conquer: check on the first half of the array since x <= z < m
3. If m < z - divide and conquer: check on the second half of the array since m < z <= y

It is easy to prove this works by using the invariant that in each iteration x <= z <= y, and that the algorithm is guaranteed to end (since size is shrinking) - giving you a guaranteed end when x == z == y (at most).