For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5.
This is just an implementation problem with a trick. Here is the approach.
- Start with first element, check if the current element matches, if so return it.
- Otherwise increment the index by the absolute difference between current element and target element.
- Repeat the above step until we find the element or reach the end of the array.
Searching for 10 in [1,2,3,4,5,6,7,8,9,10] or
Searching for 1 in [10,9,8,7,6,5,4,3,2,1]
Within One jump we reach the target element.
However this takes O(n) time in the worst case like the following
Searching for 2 in [1,1,1,1,1,1,1,1,2]
Here is the C++ implementation.