Table of Contents

## Linear Search

Linear Search in C/C++ means to sequentially traverse a given list or array and check if an element is present in the respective array or list. The idea is to start traversing the array and compare elements of the array one by one starting from the first element with the given element until a match is found or the end of the array is reached.

**Examples **:

**Input **: arr[] = {10, 20, 80, 30, 60, 50,

110, 100, 130, 170}

key = 110;

**Output **: 6

Element 110 is present at index 6

**Input **: arr[] = {10, 20, 80, 30, 60, 50,

110, 100, 130, 170}

key = 175;

**Output **: -1

Element 175 is not present in arr[].

**Problem** in Linear Search

Given an array **arr[]** of **N** elements, write a function for Linear Search in C to search a given element **X** in arr[].

#### **Algorithm**:

- Start from the leftmost element of arr[] and one by one compare X with each element of arr[].
- If X matches with an element, return the index.

If X doesn’t match with any of elements and end of the array is reached, return -1

```
// Function to linearly search the element X in the
// array arr[] of N elements
int search(int arr[], int N, int X)
{
// Pointer to traverse the array
int i;
// Start traversing the array
for (i = 0; i < N; i++)
{
// If a successful match is found,
// return the index
if (arr[i] == X)
return i;
}
// If the element is not found,
// and end of array is reached
return -1;
}
```

## Time Complexity

O(N). Since we are traversing the complete array, so in worst case when the element X does not exists in the array, number of comparisons will be N. Therefore, *worst case time complexity of the linear search algorithm is O(N)*.

## Improving the Time Complexity

We can improve the worse case time complexity to a average level.

- if element Found at last O(n) to O(1)
- if element Not found O(n) to O(n/2)

### Implementation idea

The worst case scenario occurs only when the element happens to be present in the last index. To solve this problem, we follow the below steps to average the time complexity.

- Assign the first most value to a variable called “left”.
- Likewise assign the last indexed value to a variable called “right”.
- Now as usual we run a for loop.
- Inside the for loop check for the two condition if the value-to-be-searched is either left or right most variable. If so, the task becomes simpler.
- By applying this condition, we can improve the time complexity.

### Example

Let’s see the coding in C++. The same applies for C too.

```
using namespace std;
void search(vector<int> arr, int search_Element)
{
int left = 0;
int length = arr.size();
int position = -1;
int right = length - 1;
// Run loop from 0 to right
for(left = 0; left <= right;)
{
// If search_element is found with
// left varaible
if (arr[left] == search_Element)
{
position = left;
cout << "Element found in Array at "
<< position + 1 << " Position with "
<< left + 1 << " Attempt";
break;
}
// If search_element is found with
// right varaible
if (arr[right] == search_Element)
{
position = right;
cout << "Element found in Array at "
<< position + 1 << " Position with "
<< length - right << " Attempt";
break;
}
left++;
right--;
}
// If element not found
if (position == -1)
cout << "Not found in Array with "
<< left << " Attempt";
}
// Driver code
int main()
{
vector<int> arr{ 1, 2, 3, 4, 5 };
int search_element = 5;
// Function call
search(arr, search_element);
}
```

## Conclusion

Array concept can be a very easy and interesting one when you learn to code easily. For that, you need basic knowledge. Hope this article helped you to understand the basic concepts of linear search of array!