If you want to learn about Big O : Click Here

## Linear Search:

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

**Time Complexity:** O(n) where n is the number of elements in the array, because the worst case scenario is that the element is not present in the array and we have to traverse the whole array.

## Image of Linear Search Searching an Array:

## Algorithm:

```
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
```

## Example:

```
A = [2, 4, 0, 1, 9]
x = 1
n = 5
```

### Solving the above example:

```
Step 1: i = 1
Step 2: 1 <= 5
Step 3: A[1] = 4 != 1
Step 4: i = 2
Step 5: 2 <= 5
Step 3: A[2] = 0 != 1
Step 4: i = 3
Step 5: 3 <= 5
Step 3: A[3] = 1 = 1
Step 6: Print Element 1 Found at index 3
```

## Pseudocode:

```
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure
```

## Implementation:

### C:

```
#include <stdio.h>
// Search an element in an array using linear search
void search(int arr[], int n, int x){
int i;
for(i=0; i<n; i++){
if(arr[i] == x){
printf("Element found at index %d", i+1);
return;
}
}
printf("Element not found");
}
// Main function
int main(){
int arr[] = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 35;
search(arr, n, x);
return 0;
}
```

### Java:

```
public class LinearSearchExample
{
public static int linearSearch(int[] arr, int key)
{
for(int i=0;i<arr.length;i++)
{
if(arr[i] == key)
{
return i;
}
}
return -1;
}
public static void main(String a[])
{
int[] a1= {10,20,30,50,70,90};
int key = 50;
System.out.println(key+" is found at index: "+linearSearch(a1, key));
}
}
```

### Python:

```
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = [2, 0, 1, 9]
x = 1
print("Element found at index " + str(linear_search(arr, x)))
```

### C++:

```
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int x)
{
for (int i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 2, 0, 1, 9 };
int x = 1;
int n = sizeof(arr) / sizeof(arr[0]);
int result = linearSearch(arr, n, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
```

Follow me in Github For More: Click Here

## Latest comments (0)