Search an element in an array where difference between adjacent elements is 1 - GeeksforGeeks

Search an element in an array where difference between adjacent elements is 1 - GeeksforGeeks
Given an array where difference between adjacent elements is 1, write an algorithm to search for an element in the array and return the position of the element (return the first occurrence).

The above solution can be Optimized using the fact that difference between all adjacent elements is 1. The idea is to start comparing from the leftmost element 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’ away, so instead of searching one by one, we jump ‘diff’.

The motive of this problem was to exploit the property of array ( that's if difference between adjacent elements is 1) to reduce the normal search time that is O(n) as you can see we are searching in time less than O(n).

// x is the elmenet to be searched in arr[0..n-1]

int search(int arr[], int n, int x)

{

    // Travers the given array starting from

    // leftmost element

    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

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

    }

    cout << "number is not present!";

    return -1;

}

Read full article from Search an element in an array where difference between adjacent elements is 1 - GeeksforGeeks