# Linear Search Analysis

Linear search is a simple search algorithm that is used to find a target element within a collection or data structure. It is also known as a sequential search because it sequentially compares each element in the collection with the target element until a match is found or the end of the collection is reached.

## How Algorithm of Linear Search works?

Here is the step-by-step process for implementing a linear search algorithm:

1. Start at the first element of the collection.
2. Compare the current element with the target element.
3. If the elements match, return the index of the current element.
4. If the elements do not match, move on to the next element in the collection.
5. Repeat steps 2-4 until a match is found or the end of the collection is reached.
6. If the end of the collection is reached without finding a match, return a message indicating that the target element is not in the collection.

In summary, linear search is a simple search algorithm that sequentially compares each element in a collection with a target element until a match is found or the end of the collection is reached. It is easy to understand and can be used with any type of collection, but it may be inefficient for large collections.

Here is the pseudocode for linear search:

``````linear_search(collection, target):
for each element in collection:
if element equals target:
return true
return false
``````

In this pseudocode, the `collection` parameter represents the collection of elements that we want to search, while the `target` parameter represents the element that we want to find within the collection. The algorithm works by iterating through each element in the collection one by one, and checking whether it is equal to the target element. If a match is found, the function returns `true`. If the end of the collection is reached and no match is found, the function returns `false`.

Here’s an example of how the linear search algorithm works:

Suppose we have the following collection of numbers.

``[6, 4, 9, 2, 3, 7, 5, 8, 1]``

And we want to find the index of the number 7 in the collection.

1. Set index to 0
2. While index is less than the length of the collection (which is 9 in this case), repeat steps 3-4:
• Index = 0: The current element is 6, which is not equal to 7, so we move to the next element.
• Index = 1: The current element is 4, which is not equal to 7, so we move to the next element.
• Index = 2: The current element is 9, which is not equal to 7, so we move to the next element.
• Index = 3: The current element is 2, which is not equal to 7, so we move to the next element.
• Index = 4: The current element is 3, which is not equal to 7, so we move to the next element.
• Index = 5: The current element is 7, which is equal to the target element, so we return the index 5 and terminate the search.

The linear search algorithm found the target element 7 at index 5, and it took 6 comparisons (iterations) to do so.

### Example Code

Here’s an example of a C++ program that performs linear search:

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

int linearSearch(int arr[], int n, int target)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == target)
{
return i; // return the index of the target element
}
}
return -1; // return -1 if the target element is not found
}

int main()
{
int arr[] = {5, 10, 15, 20, 25, 30};
int n = sizeof(arr) / sizeof(arr);
int target = 20;
int index = linearSearch(arr, n, target);
if (index != -1)
{
cout << "Element found at index " << index << endl;
}
else
{
}
return 0;
}
```

The above program will output:

``Element found at index 3``

In this program, we define a function `linearSearch` that takes an integer array `arr`, its size `n`, and a target integer `target`. The function returns the index of the target element in the array, or -1 if the target element is not found. The function works by iterating over the elements of the array one by one, and comparing each element with the target element. If the target element is found, the function returns its index.

## Complexity Analysis of Linear Search

The time complexity of linear search algorithm is O(n), where n is the number of elements in the collection being searched.

This means that in the worst case scenario, the algorithm will need to look at every element in the collection to determine if the target element is present or not. In the average case, the algorithm may only need to examine half of the collection before finding the target element.

However, the space complexity of linear search is O(1), because the algorithm only needs to store a few variables (like the index and the target element) in memory at any given time.

It’s important to note that linear search is a simple and straightforward algorithm, but it may not be efficient for very large collections. In cases where the collection is sorted or has some other structure, there may be more efficient search algorithms available, such as binary search. Nonetheless, linear search remains an important algorithm to know and understand, as it is often used as a baseline for comparison with more complex search algorithms.

## When is the Linear Search algorithm used?

Linear search is used when the collection of elements is small or unsorted, and we need to find the presence of a specific element in the collection. It is a simple and easy-to-understand algorithm that works by scanning each element of the collection one by one until the target element is found.

Linear search is particularly useful in cases where the collection of elements is constantly changing, and there is no time to sort the collection before searching for an element. For example, linear search could be used to search for a specific word in an unsorted text file.

Linear search is also a useful algorithm for educational purposes, as it provides a good starting point for learning about search algorithms and their complexities. In addition, linear search can be useful as a baseline for measuring the efficiency of more complex search algorithms, such as binary search or hash table lookup.

• Linear search is a simple and easy-to-understand algorithm, making it ideal for beginners learning about search algorithms.
• Linear search is effective when searching for a single occurrence of a specific element in a small or unsorted collection of elements.
• Linear search can be implemented using a small amount of memory, making it suitable for use in memory-constrained environments.