Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?

For example consider the array `{1, 2, 1, 2, 3, 2, 3, 4, 5, 6}`

, and we want to search for the number 5.

The simplest solution is to check if the number is present or not using linear search. This algorithm takes O(n) time in the worst case.

But we are not utilizing the fact that the adjacent numbers differ by 1.

How do we utilize this property to improve the performance?

Let us assume we are searching for a number x+3 in an array.

Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have

`x, x+1, x+2, x+3, ...`

x, x+1, x, x+1, ...

x, x-1, x, x+1, ...

x, x-1, x-2, x-1, ...

x, x+1, x+2, x+1, ...

etc...

We can safely jump to index 3 and check if the number is present. Why? Because in any pattern there is no chance of having x+3 before the index 3.

If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.

The time complexity of the above procedure is still `O(n)`

, because in the worst case, we make n/2 jumps. But this is an improvement over the linear search (n comparisons in the worst case).

Example, search for number 6 in the array `{4, 5, 4, 5, 4, 5, 4, 5, 4, 5}`

, we have to make 5 jumps to conclude that 6 is not present.

Here is the C++ implementation of the same.

Algorithms / Arrays / Search