Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Time complexity
2.2.2.
Space complexity
3.
Optimized 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.
Which searching technique is best for unsorted arrays?
4.2.
Which case has the best time complexity for searching an element in an unsorted array?
4.3.
Is binary search good for unsorted?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Search an Element in an Unsorted Array using Minimum Number of Comparisons

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Searching an element in an unsorted array using a minimum number of comparisons is an array medium-level problem. It is a well-known practice problem for learning problem-solving and time complexity optimization. It had also been asked in the Adobe interview.

In this article, we’ll use the methods of Brute Force and then Optimize our approach to solve this problem.

Problem Statement 

We are given a set of n distinct integers and an element x. We are supposed to find if element x is present in the array keeping the comparison as minimum as possible. Any type of comparison will add one to the total number of comparisons.

Sample Examples

Example 1

Input

Array

x = 9

Output

Found

Explanation

Element 9 is present in the array, we print Found.

 

Example 2

Input

Array

x = 15

Output

Not Found

Explanation

Since the element cannot be found in the array, we print: Not Found.

Brute Force Approach

We initialize the element we want to search as the first element and then traverse the array, comparing each element.

  1. Run a for loop for i<size of given array.
  2. if (arr[i]==x) return the index.
  3. Else the element is  not present in the array.

Pseudocode

for (i = 0; i < n; i++)  // Worst case n+1 Comparisons
   if (arr[i] == x)  // Worst case n comparisons
       return i;


Comparison Count

In the worst-case scenario, we perform two comparisons at each step of the loop. Total number of comparisons (in worst-case scenario): 2n+1 Comparisons

=> (n+1) + n  = 2n + 1.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

string search(int a[], int n, int element)
{
	for (int i = 0;i<n; i++)  // executes n+1 times
	{
		if(a[i] == element) // atmost n comparisons
		return "Found";
	}
		return "Not Found";
}

int main()
{
	int a[] = { 8, 7, 3, 6, 9 };
	int size = sizeof(a) / sizeof(a[0]);
	int element = 9;
	cout << search(a, size, element);
	return 0;
}

 

Output

Found

Time complexity

The complexity will be O(n), as the total number of comparisons are (2n+1) to decide if the element x is present in the array or not.

Space complexity

The complexity will be O(1), as no extra space is used.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

The goal is to copy the element to be searched to the last location so that a last comparison is saved if x is not found in the array. We can understand it better using the Pseudocode presented below.

Pseudocode

search(a[], n, x)
    if arr[n-1] == x // 1st comparison
       return 1
    last = arr[n-1]
    a[n-1] = x

    for i=0, i++
        if a[i] == x // execute n times (n comparisons)
            arr[n-1] = last
            return (i < n-1) // last comparison


Hence total comparison = 1st comparison + n loop execution + 2nd comparison

    = n+1+1 = n+2 total comparison

Comparison Count

Atmost (n+2) comparisons are needed to decide if the element x is present in the array or not. However, in this approach, we reduced our comparisons from that of the naive approach i.e., 2n+1.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;


string search(int a[], int n, int element)
{
// 1st comparison
if (a[n - 1] == element)
return "Found";


int last = a[n - 1];
a[n - 1] = element;

for (int i = 0;; i++)  // executes n times (but no comparisons executed)
{
        if(arr[i] == element){ // atmost n comparisons
            a[n - 1] = last;


            if (i < n - 1)  //2nd comparison
                return "Found";
            return "Not Found";
        }
}
}

int main()
{
int a[] = { 8, 7, 3, 6, 9 };
int size = sizeof(a) / sizeof(a[0]);
int element = 9;
cout << search(a, size, element);
return 0;
}


Output

Found

Time complexity

The time complexity of the approach will be O(n), as we are determining where element is present or not in a single loop.

Space complexity

The complexity will be O(1), as no extra space is used.

Read More - Time Complexity of Sorting Algorithms and  Rabin Karp Algorithm

Frequently Asked Questions

Which searching technique is best for unsorted arrays?

The best way to find a value in an unsorted array is to use sequential search.
 

Which case has the best time complexity for searching an element in an unsorted array?

When an element is the first or last element in an array, the best case complexity is O(1).
 

Is binary search good for unsorted?

No, the binary search needs a sorted array.

Conclusion

This article discussed the problem of searching an element in an unsorted array using a minimum number of comparisons.

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 TheoryBook Allocation Problem, 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!

Previous article
Search an element in an array where difference between adjacent elements is 1
Next article
Square Root using binary search
Live masterclass