Problem solving with programming: Searching for an element in array with successive elements atmost 1 distance apart

Problem solving with programming: 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.

int search_step_array(vector<int>& arr, int s)


{


 int result = -1;


 int i;


 for( i = 0; i < arr.size(); )


 {


  if( arr[i] == s )


  {


   result = i;


   break;


  }


  else


  {


   i += abs(arr[i]-s);


  }


 }


 return result;


}

Read full article from Problem solving with programming: Searching for an element in array with successive elements atmost 1 distance apart