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.
- Run a for loop for i<size of given array.
- if (arr[i]==x) return the index.
- 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
FoundTime 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.
24+ registered 
