# What could be the most efficient algorithm to find index in an array that matches given conditions?

I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1].

Example:

A = [12,11,9,7,5,54,67,87,23,54,20,22]


Should return 4 because subarray [7,5,54] matches the condition where A[4] = 5.

Below is the solution I tried. It has run time O(n). I am looking if there is any other better solution?

 def sol_1():
for j in range(1,n):
if A[j-1]>=A[j] and A[j]<=A[j+1]:
return j
return False

• what about the indexes $1$ and $n$. What is the satisfying conditions for them? Sep 19, 2021 at 9:15
• Do you have any reason to suspect there might be a "better" solution? And what do you mean with "better"? Sep 19, 2021 at 10:28
• You say "Should return 4" but then you actually only return True or None. Which one is it? Sep 19, 2021 at 10:31
• Before efficiency, I suggest you first make it correct. For example for n = 3 A = [1,2,1] your code crashes. Sep 19, 2021 at 10:35
• Should return 4 What about 10, 8? Sep 20, 2021 at 7:42

You can not do better than $$n-2$$ in the worst case. You can show this using an adversarial argument.
Suppose the array is $$A = [1,2,3,\dotsc,n]$$. There is no index in the array that satisfies that $$A[i-1] \geq A[i] \leq A[i+1]$$. Therefore, the answer is trivially no. For the sake of contradiction assume that there is an algorithm that solves the problem in less than $$n-2$$ operations. It means there is an index of the array that is not accessed by the algorithm. Suppose this index is $$t$$ and $$1. Since the algorithm has not seen this index yet, the adversary can decrease $$A[t]$$ value by $$1$$, i.e., $$A[t] = t-1$$. Now, index $$t$$ satisfies that $$A[t-1] \geq A[t] \leq A[t+1]$$; thus proving the algorithm wrong.
Therefore, any correct algorithm must access at least $$n-2$$ entries of the array. Therefore, the lower bound on the running time is $$\Omega(n)$$.