Searching in a step array

 

in a step array every element has a difference of at most k with its neighbor.

we should search an element x in this array ,if more than one occurance exist return the first occurrence of the key.

Input : arr[] = {4, 5, 6, 7, 6}
           k = 1
           x = 6
Output : 2
The first index of 6 is 2.

Input : arr[] = {20, 40, 50, 70, 70, 60}  
          k = 20
          x = 60
Output : 5
The index of 60 is 5

method 1:

just traverse the whole array one by one using lineaer search, the time complexity will be 0(n)

method 2:

we can use the idea that difference between all adjacent elements is at most k and optimize the solution. start from the first element and compare with the element to be searched ie x, and find the difference between current array element and x. Let this difference be ‘diff’. From the given property of array, we always know that x must be at-least ‘diff/k’ away, so instead of searching one by one, we jump ‘diff/k’.

implementation:

int search(int arr[], int n, int x, int k) 
{ 
    
    // start from first index 
    int i = 0; 
    while (i < n) 
    { 
        // If x is found at index i 
        if (arr[i] == x) 
            return i; 
  
    // Jump the difference between current array element and x divided by k 
    // We use max here to make sure that i 
    // moves at-least one step ahead. 
        i = i + max(1, abs(arr[i]-x)/k); 
    } 
  
    // if number is not present 
    return -1; 
}