## 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**

`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.