Search an array where adjacent differ by at most k

A step array is an array of integers where each element has a difference of at most k with its neighbour.

We have given a step array arr, k and key x, Our task is to find the index value of x if multiple elements exist to return the first occurrence of the key.

Example 1

Input: arr[] = {4, 5, 6, 7, 6}

           k = 1

           x = 6

Output: 2

The first index of 6 is 2.

Example 2

Input: arr[] = {20, 40, 50, 70, 70, 60}  

          k = 20

          x = 60

Output: 5

The index of 60 is 5

Approach

To efficiently find the index of a given element 'x' in an array where adjacent elements have a difference of at most 'k', we can optimize the search process. Instead of checking each element one by one, we leverage the fact that the difference between adjacent elements is limited to 'k'.

The following are the steps to implement this logic:

1. Begin the comparison from the leftmost element of the array.
2. Calculate the difference ('diff') between the current array element and 'x'.
3. Since the array is a step array, we know that 'x' must be at least 'diff/k' away.
4. Instead of checking each element one by one, jump 'diff/k' steps.
5. Repeat this process until a match is found or the end of the array is reached.

This optimized approach reduces the number of comparisons needed, making the search more efficient, especially for large arrays with a step pattern.

Complexity

• Time Complexity: O(N), where n is the number of elements in the array.
• Space Complexity: O(1)

Code

# Java Code

public class StepArraySearch {

    public static int searchInStepArray(int[] arr, int n, int k, int x) {

        int i = 0;
        while (i < n) {
            if (arr[i] == x) {
                return i;
            }

            int diff = Math.abs(arr[i] - x);

            // Move to the next index based on the difference
            i = i + Math.max(1, diff / k);
        }
        return -1; // Key not found
    }

    public static void main(String[] args) {
        // Example usage:
        int[] arr1 = {4, 5, 6, 7, 6};
        int k1 = 1;
        int x1 = 6;
        int n1 = arr1.length;

        int result1 = searchInStepArray(arr1, n1, k1, x1);
        System.out.println("Output 1: " + result1); // Output: 2

        int[] arr2 = {20, 40, 50, 70, 70, 60};
        int k2 = 20;
        int x2 = 60;
        int n2 = arr2.length;

        int result2 = searchInStepArray(arr2, n2, k2, x2);
        System.out.println("Output 2: " + result2); // Output: 5
    }
}

Output

Output 1: 2

Output 2: 5