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

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) {
}

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.