Search for a Key in an Array in which consecutive numbers differ by +1/-1

Question

Given a one-dimensional array. Each number of this array differs from the pervious number by +1 or -1. Example: Array {5,6,7,6,5,6,7,8,9,8}

You are given a number to search its first occurrence in this array (example: search for 8 -- Your code should return 7). Do not use Linear Search.

Without Linear Search, I could have tried it as follows:

Check if (array[0] == Key)
{
        YES:
           return 0;
}

Take a variable: Diff = array[0]

// Keep on traversing the array, if Next Number>Current Number
   Diff += 1
   Else
   Diff -= 1

if (Diff==key)
{
    return current_index+1;
}

But this method is too generic. Even if the difference between the keys is NOT +-1 but something else, this method will solve this problem.

What is so specific about +-1 difference, which can give me a better solution?

Thanks.

Answer 1

Say you're searching for 16, and array[0] = 8. This means that the number you're searching for can't appear before array[8], i.e. (target - array[0]). So you read array[8], which has 13; that means that the target can't appear before array[11]. And so on. The +/- 1 difference lets you skip ahead in your search, because you know that if array[x] = (target +/- N) that the target number can't appear before array[x + N].

Answer 2

You don't need to look at every number in the list. Say you are looking for 8, and the first number is 5. You can safely step 3 since 8 cannot occur in less than three steps. You might consider stepping slightly more - say 6 - since there are probably some -1's, but I don't know if that would be more efficient, since you would not be sure it is the "first" occurrence then. So let's stick with the original:

When you get to the new number you determine what size step to take next - in the above if you had taken a step of 3 you would have found 6, step another 2 (8-6) and you find 6 again, step another 2 and you find 8 - you are there! You know it is the first occurrence since the numbers you skipped could not have been 8. And it only took three steps instead of seven.