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;
}

You can also try this code with Online C++ Compiler
Run Code
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!