How to find a search algorithm that is faster than O(n) time

Assume a 1-indexed array A[1…n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1.

Develop an efficient recursive algorithm to find j such that A[j] = z, where A[1] ≤ z ≤ A[n]. The algorithm must be more efficient that O(n).