## Approach

We can optimize the above approach by using the fact that there is a one-to-one difference between all neighbouring elements. The goal is to identify the difference between the current array element and the element to be searched let's say num, by traversing and comparing from the leftmost element. Let this difference be diff. We always know that num must be at least ‘diff’ away because of this feature of the array, thus instead of searching one by one, we go straight to diff.

### Pseudocode

```
int search(int arr[], int n, int element)
{
// Traverse the given array starting from
// leftmost element
int i = 0;
while (i<n)
{
if (arr[i] == element)
return i;
i +=abs(arr[i] - element);
}
cout << "number is not found";
return -1;
}
```

### Implementation in C++

```
#include<bits/stdc++.h>
using namespace std;
int search(int a[], int size, int element)
{
int i = 0;
while (i<size)
{
if (a[i] == element)
return i;
// FInding the difference between curr element and target element
i += abs(a[i]-element);
}
return -1;
}
int main()
{
int a[] = {3, 4, 3, 2, 3, 4 };
// size of the array
int size = sizeof(a)/sizeof(a[0]);
// element to be searched
int element = 2;
// function for getting index
int pos=search(a,size,element);
if(pos>=0)
cout << "Element " << element << " found at index " << pos;
else
cout<<"Element is not found";
return 0;
}
```

**Output**

Element 2 found at index 3

#### Time Complexity

The time complexity of the program is O(n), as we are traversing the whole array, where n is the length of the array.

#### Space complexity

The space complexity of the program is O(1) because the program is not using any auxiliary space.

## Frequently Asked Questions

**Is array a data type?**

**The array data type is a compound data type** represented by the number 8 in the database dictionary. Arrays store a list of elements of the same data type accessed by an index (element) number. The term array is synonymous with the terms list, vector, and sequence.

**What is array in DSA?**

An array is **a linear data structure that collects elements of the same data type and stores them in contiguous and adjacent memory locations**.

**What is the time complexity for linear traversal in an array?**

The time complexity is O(n), where n is the size of the array.

## Conclusion

This article extensively discussed the problem of searching for an element in an array where the difference between adjacent elements is 1. We solved the problem using a tricky construction and a critical observation.

We hope this blog has helped you enhance your knowledge regarding array problem-solving. Are you interested in reading/exploring additional articles about this topic? Don't worry; Coding Ninjas has you covered. See __Time Complexity and Analysis__, __Sorting Based Problems__, __Number Theory__, and__ Dynamic Programing__ to learn.

**Recommended problems -**

Refer to our __Guided Path__ on __Coding Ninjas Studio__ to upskill yourself in __Data Structures and Algorithms__, __Competitive Programming__, and many more! You can also check __Interview Experiences__ and __Interview Preparation Resources__ if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Do upvote our blogs if you find them helpful and engaging

**Happy Learning!**