Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.2.1.
Time Complexity 
3.2.2.
Space complexity 
4.
Frequently Asked Questions
4.1.
Is array a data type?
4.2.
What is array in DSA?
4.3.
What is the time complexity for linear traversal in an array?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

It is a simple array search problem to find an element in an Array where the difference between adjacent elements is 1. It is a well-known practice problem for learning problem-solving and time complexity optimization.

In this article, we’ll use the methods of Search and Traverse to solve this problem.

Also see, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

We are given an array where the difference between adjacent elements is 1. Create an algorithm that searches the array for the first occurrence of such an element and returns its index.

Sample Examples

Output Format: We will be returning the index of the element.

Example 1

Input

Array

Element: 2

Output

Element 2 found at index 3

Explanation

The element 2 is found at index 3.

 

Example 2

Input

Array

 Element: 7

Output

Not Found

Explanation

Since 7 is not present in the array hence we print: Not Found.

Note: The brute force approach is to search and traverse each array element and compare it to the given element. If there are any matches, return the index. In this article, we will be discussing the optimized approach.

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 AnalysisSorting Based ProblemsNumber Theory, and Dynamic Programing to learn.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive 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!

Live masterclass