In Progress
Lesson 7, Topic 1
In Progress

# Linear Search

Lesson Progress
0% Complete

Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.

## Implementing Linear Search

Following are the steps of implementation that we will be following:

1. Traverse the array using a `for` loop.
2. In every iteration, compare the `target` value with the current value of the array.
• If the values match, return the current index of the array.
• If the values do not match, move on to the next array element.
3. If no match is found, return `-1`.

To search the number 1 in the array given below, linear search will go step by step in a sequential order starting from the first element in the given array.

Start from the first element, compare k with each element x.

If `x == k`, return the index.

## Linear Search Algorithm

``````LinearSearch(array, key)
for each item in the array
if item == value
return its index``````

### Linear Search Program in C

``````// Linear Search in C

#include <stdio.h>

int search(int array[], int n, int x) {

// Going through array sequencially
for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}

int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array);

int result = search(array, n, x);

(result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}``````

## Linear Search Complexities

Time Complexity: O(n)

Space Complexity: `O(1)`

## Linear Search Applications

1. For searching operations in smaller arrays (<100 items).