Finding an element within an array that satisfies some rule

Question

I saw a question on an old exam in my university course of DSA and I am not sure if the question is far too easy or if I am missing something.

The question is :

Given an array A that consists of N integers such that for any 1ドル < i \leq N$ the following properties holds :

• $| A[i] - A[i-1] | \leq 1$
• $ A[N] > A[1] $

Given an element z such that A[1] $\leq$ z $\leq$ A[N], Write an efficient search algorithm and analyze its complexity.

I started thinking about this problem and after a few minutes, I found that from the fact we have A[1] < A[N] and that the absolute value of the difference between 2 consecutive elements has to be at most one, we can deduce that our array must contain all the values between A[1] and A[N], therefore the algorithm should only check if z is between A[1] and A[N].
Am I missing something?

• nir shahar: You need to find the index of the element, not whether it exists or not.
• Yarin: @nirshahar shahar Yes of course it could be increasing and then decreasing but eventually, it has to attain some value A[N] which has to be greater than A[1]. So we can say for sure that if z is an element between A[1] and A[N] it has to be in the array, am I missing something?
• Yarin: @nirshahar Gotcha, it really might be finding the index of the element, so maybe I can implement some variation of binary search here? EDIT: the thing is that a given element between A[1] and A[N] could appear as many times as we want because the values can oscillate up and down as long as in the end we will attain A[N], guess I'll have to think about it more
• user16034: The question is incomplete: does "search" mean to find a single occurrence, or all of them ?
• user16034: By the way, your "easy solution" to the existence problem is wrong: z could be in the array even if not between A[1] and A[N].

Answer 1

Lets say a[1] = 1, a[N = 1000] = 2, and z = 450. The first array element that could equal z is a[450], and the last one is a[552]. Since 450 ≤ 552, there could be a solution.

So you have reduced the range. Now check the values a[450] and a[552]. Either one of them is equal to z, or you can reduce the range again. Now the worst case is that you have a large range of values equal to z-1, and there might or might not be one equal to z in the range. Solving this will require linear time. Bad example:

a[1] = 1, a[2] .. a[N = 1000] = 2 except perhaps a[k] = 3, and z = 3. You have to check every value.

• Yarin: Please note that they're asking about a given z which satisfies A[1] $\leq$ z $\leq$ A[N]

Answer 2

The proposed approach by @gnasher729 is true. Maybe the following commands clarify it.

Let L=1 and U=N for the lower and upper range of the search area in array A.

1. Repeat the following commands:
2. If L>U then Z does not exist in array A and terminate.
3. If Z==A[L] or Z==A[U] then we found Z and terminate.
4. Else, reduce the search area by L=Z-A[L] and U=A[U]-Z; i.e. Z cannot be found before index Z-A[L] and after index A[U]-Z.