Efficiently finding an element in in an array where consecutive elements differ by +1/0/-1

Question

I have this problem, that I feel I am vastly overcomplicating. I feel like this should be incredibly basic, but I am stumbling on a mental block.

The question reads as follows:

Given an array of integers A[1..n], such that A[1] ≤ A[n] and for all i, 1 ≤ i < n, we have |A[i] − A[i+ 1]| ≤ 1. Devise an semi-efficient algorithm (better in the worst case then the native case of looking at every cell in the array) to find any j such that A[j] = z for a given value of z, A[1] ≤ z ≤ A[n].

My understanding of the given array is as follows: You have an array that is 1-indexed where the first element of the array is smaller than or equal to the last element of the array. Each element of the array is with in 1 of the previous one (So A[2] could be -1, 0, or +1 of A[1]'s value).

I have had several solutions to this question all of which have had there issues, here is an example of one to show my thought process.

i = 2
while i <= n {
    if (A[i] == x) then 
        break // This can be changed into a less messy case where
              // I don't use break, but this is a rough concept
    else if (abs(A[i] - j) <= 1) then 
        i--
    else 
        i += 2

}

This however fails when most of the values inside the array are repeating. An array of [1 1 1 1 1 1 1 1 1 1 2] where searching for 2 for example, it would run forever.

Most of my attempted algorithms follow a similar concept of incrementing by 2, as that seems like the most logical approach when dealing with with an array that is increasing by a maximum of 1, however, I am struggling to find any that would work in a case such as [1 1 1 1 1 1 1 1 1 1 2] as they all either fail, or match the native worst case of n.

I am unsure if I am struggling because I don't understand what the question is asking, or if I am simply struggling to to put together an algorithm.

What would an algorithm look like that fits the requirements?

Answer 1

This can be solved via a form of modified binary search. The most important premises:

• the input array always contains the element
• distance between adjacent elements is always 1
• there's always an increasingly ordered subarray containing the searched value

Taking it from there we can apply two strategies:

• divide and conquer: we can reduce the range searched by half, since we always know which subarray will definitely contain the specified value as a part of an increasing sequence.
• limiting the search-range: suppose the searched value is 3 and the limiting value on the right half of the range is 6, we can then shift the right limit to the left by 3 cells.

As code (pythonesque, but untested):

def search_semi_binary(arr, val):
    low, up = 0, len(arr) - 1
    while low != up:
        # reduce search space
        low += abs(val - arr[low])
        up -= abs(val - arr[up])

        # binary search
        mid = (low + up) // 2

        if arr[mid] == val:
            return mid
        elif val < arr[mid]:
            # value is definitely in the lower part of the array
            up = mid - 1
        else:
            # value is definitely in the upper part of the array
            low = mid + 1

    return low

The basic idea consists of two parts:
First we can reduce the search space. This uses the fact that adjacent cells of the array may only differ by one. I.e. if the lower bound of our search space has an absolute difference of 3 to val, we can shift the lower bound to the right by at least three without shifting the value out of the search window. Same applies to the upper bound.
The next step follows the basic principle of binary search using the following loop-invariant:
At the start of each iteration there exists an array-element in arr[low:up + 1] that is equal to val and arr[low] <= val <= arr[up]. This is also guaranteed after applying the search-space reduction. Depending on how mid is chosen, one of three cases can happen:

• arr[mid] == val: in this case, the searched index is found
• arr[mid] < val: In this case arr[mid] < val <= arr[up] must hold due to the assumption of an initial valid state
• arr[mid] > val: analogous for arr[mid] > val >= arr[low]

For the latter two cases, we can pick low = mid + 1 (or up = mid - 1 respectively) and start the next iteration.