ronith
6/19/2018 - 6:25 PM

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

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).

Examples :

Let element to be searched be x

Input: arr[] = {8, 7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3}
x = 3 Output: Element 3 found at index 7

Input: arr[] = {1, 2, 3, 4, 5, 4} x = 5 Output: Element 5 found at index 4

A Simple Approach is to traverse the given array one by one and compare every element with given element ‘x’. If matches, then return index.

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’.

Search an element in an array where difference between adjacent elements is 1.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/search-an-element-in-an-array-where-difference-between-adjacent-elements-is-1/

#include <iostream>
using namespace std;

int main() {
    int n,x;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];
    cout<< "Enter the search element: ";
    cin >> x;

    int i=0;
    while (i<n){
        if (a[i]==x){
            cout<< "Index is: "<<i;
            exit(0);
        }
        i+=abs(a[i]-x);
    }
    cout<< "Element is not present!";

}