## Things we will discuss here

- Introduction
- Linear Search Algorithm
- Time and Space Complexity
- C++ Implementation
- Practice Problems

## Introduction

Linear search is a Search Algorithm as the name suggests. It is used on a collection of items. It relies on the technique of traversing a list from start to end by exploring the properties of all the elements that are found on the way.

## Linear Search Algorithm

- Take a collection of elements and let
**k**(be the value to be searched for). - Now traverse (go through all the elements) the collection and check whether that element is equal to
**k**or**not**.- If equal then print “Found” and break the loop.
- Else go till the last element and if not found then print “Not Found”.

**Example:** Taking an array of **9 elements** and searching for **4** in it.

**Time and Space Complexity**

**Time Complexity**

- In this, in the worst case, we will be going to all the elements.
- Hence the complexity is O(n) where n-number of elements in a collection.

**Space Complexity**

- Here we need to store all the
**n elements**in an array before searching so the space complexity it**O(n)**.

## C++ Implementation

```
#include <bits/stdc++.h>
using
```**namespace** std;
**int** main() {
**int** n;* // Number of element*
cin >> n;
vector<**int**> arr(n);* // Declaring array of size n.*
for (**int** i = 0; i < n; i++) cin >> arr[i];
**int** k;* // Number to be searched for in the array.*
cin >> k;
**bool** found = false;* // found = true if number is present in array.*
for (**int** i = 0; i < n; i++) {
if (arr[i] == k) {
cout << "Found\n";
found = true;
break;
}
}
* // if number is not present.*
if (!found) {
cout << "Not Found\n";
}
return 0;
}

**Input 1**

```
5
1 2 3 4 5
4
```

**Output 1**

`Found`

**Input 2**

```
5
1 2 3 4 5
7
```

**Output 2**

`Not Found`

## Practice Problems

If you have some **content OR material** related to this **OR there is an error** then do share them through the comment section for which we will be thankful to you.

Thank You for Reading