Tuesday, March 31, 2015

Searching for an element in array with successive elements atmost 1 distance apart

Given an array of integers where each element has a difference of atmost 1 with it's neighbors, we need to find the given element.

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.
This algorithm runs in O(1) in best case. Example of the base cases
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.