# Linear Search in C++

## Linear Search in C

Linear search is one of the simplest algorithms of data structure.

• The element to be searched is compared with every element of the list one by one
• Until the element that is to be searched is found.
• If the element is not found till the end this means that the element is not present in the list.
 Time Complexity O(n) Best Case O(1) Worst Case O(n) Space Complexity O(1) Avg. Comparisons (n+1)/2

## Algorithm to implement linear search in C++

1. Read the item to be searched by the user.
2. Compare the search element with the first element in the list.
3. If they both matches,  terminate the function.
4. Else compare the search element with the next element in the list.
5. Repeat steps 3 and 4 until the element to be search is found.

## Program to implement linear search algorithm in C++

Run

```#include<iostream>
using namespace std;

void LinearSearch(int arr[], int len, int item){

for(int i=0;i<len;i++){
if(arr[i] == item){
cout << item << " Found at index : " << i;
return;
}
}

}

int main() {
int arr[] = {10, 5, 15, 21, -3, 7};

// calculating length of array
int len = sizeof(arr)/sizeof(arr[0]);

// item to be searched
int item = 21;
LinearSearch(arr, len, item);

return 0;
}
// space complexity: O(N)
// time complexity : O(N)```

### Output:

```21 Found at index : 3
```

## Method 2 (Using Recursion)

This method uses recursion in c++

Run

```// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include<iostream>
using namespace std;

int LinearSearch(int arr[], int index, int item)
{
if(arr[index] == item)
return index;
else if (index == -1)
return -1;

return LinearSearch(arr, index - 1, item);
}

int main()
{
int arr[] = {10, 5, 15, 21, -3, 7};

// calculating length of array
int len = sizeof(arr)/sizeof(arr[0]);

// item to be searched
int item = 21;

int index = LinearSearch(arr, len - 1, item);

if(index >= 0)
cout << "Item found at index: " << index;
else

return 0;
}```

### Output

`Item found at index: 3`

## Linear search and Binary Search Comparison

• Linear search (Time complexity): O(n)
• Binary search (Time complexity): Log(n)

O(1)

O(n)

O(n)

O(1)

(N+1)/2