# Linear Search in C

Linear search in C is a searching method/algorithm. In the linear search algorithm, we traverse through the data structure from any one point and traverse until the data item is found in the data structure.

These data structures could be array, string, Linked-List, Stack, Queue, or any other data structure.

Linear Search Example:

Find the number 34 in the given data structure Array.

Array:

 24 56 -1 90 4 12 34 89 37 0 1 2 3 4 5 6 7 8

Solution:

Index Number Working
0 24 24 != 34 * We will continue our search
1 56 56 != 34 *We will continue our search
2 -1 -1 != 34 => We will continue our search
3 90 90 != 34 => We will continue our search
4 4 4 != 34 => We will continue our search
5 12 12 != 34 => We will continue our search
6 34 34 == 34 => As a result, we have ended our search
7 89
8 37

Because 6 is the index of our element (34), our answer is 6 for 0-based indexing arrays and 7 for 1-based indexing arrays. This is how linear search works in an array.

Problem Description

Write a C Program which finds the position of an element in an array using Linear Search Algorithm. We have to take an array and a value to be searched in the array as input from the user, and then find the position of that element in array by using linear search algorithm.

Problem Solution

1. We will create an array of numbers by taking input from user. We will also read the element to be searched by the user.
2. In order to look for that element in the array, we’ll go sequentially in increasing index values. If we encounter the element requested by the user we will return the position of that element in array, but if it is not there we will return -1 which indicates the absence of element which was searched.

Linear Search Algorithm:

Input: An array A[1..n] of n elements and an element x to be found and output its position.
Output:

```J if x = A[j], 1 ≤ j ≤ n, and 0 otherwise.
J := 1
while J<n && A[J] ≠ x
j := j+1
end while
if A[J] = x then return J Else return 0```

There are several ways to implement Linear Search in C language. Let’s take a detailed look at all the approaches to implement Linear Search algorithm.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Method 1: Linear Search in C using Array

In this approach, we will find if an element X is present in the array or not and if yes find its position pos using array.

An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number.

Expected Input and Output

1. Average Case: If the searched element is other than the first and the last element of the array.
For example:

```If the input array is {4, 6, 1, 2, 5, 3}
and if the element searched is 6,
then the expected output will be Position 2.```

Average case time complexity: O(n)

2. Best Case: If the searched element is the first element of the array.
For example:

```If the input array is {66, -3, 31}
and the key searched for is 66,
then the expected output will be Position 1.```

Best case time complexity: O(1)

3. Worst Case: If the element searched for is the last element of the array.
For example:

```If the input array is {1, 3, 6, 1, 9}
and the key searched for is 9,
then the expected output will be Position 5.```

Worst case time complexity: O(n)

Program/Source Code

Here is source code of the C Program to find the position of an element requested by the user using Linear Search Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

1. `/*`
2. ` * C program to input N numbers and store them in an array.`
3. ` * Do a linear search for a given key and report success or failure.`
4. ` */`
5. ` `
6. `#include <stdio.h>`
7. ` `
8. `void main()`
9. `{  int num;`
10. ` `
11. `    int i,  keynum, found = 0;`
12. ` `
13. `    printf("Enter the number of elements ");`
14. `    scanf("%d", &num);`
15. `    int array[num];`
16. `    printf("Enter the elements one by one \n");`
17. `    for (i = 0; i < num; i++)`
18. `    {`
19. `        scanf("%d", &array[i]);`
20. `    }`
21. ` `
22. `    printf("Enter the element to be searched ");`
23. `    scanf("%d", &keynum);`
24. ` `
25. `    /*  Linear search begins */`
26. `    for (i = 0; i < num ; i++)`
27. `    {`
28. `        if (keynum == array[i] )`
29. `        {`
30. `            found = 1;`
31. `            break;`
32. `        }`
33. `    }`
34. `    if (found == 1)`
35. `        printf("Element is present in the array at position %d",i+1);`
36. `    else`
37. `        printf("Element is not present in the array\n");`
38. `}`
Program Explanation

1. 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.
2. The array is searched sequentially and the position is returned if the key element to be searched is available in the array, otherwise -1 is returned.
3. Here in this C Program we have not made any function specifically for linear search, rather we can look for presence of element in an array in the main function itself.
4. We traverse the array from the 0th index in increasing order of index, if we find the element we break the loop there itself and print the position of the element in the array, but if the element requested is not there in array, we simply print that “Element is not present in the array”.
5. If we’d have created a separate function for linear search and the element could not be found in the array, we would have returned -1 in that case denoting absence of the element.

Time Complexity:

Average & Worst Case: O(n)
As the name suggests it is a linear search and we used a loop to iterate over the array from start to end, hence we can affirm that it is of O(n) complexity.

Best Case: O(1)
The best-case complexity will be found if you find the element at the first index from the start *(according to the approach we used). It can be denoted as O(1)

Space Complexity: O(n + k)
space complexity of the linear search algorithm is O(n + k), where n = size of the array and k = auxiliary variables.

Runtime Test Cases

Test Case 1: In this case, we use the linear search algorithm to find the position of element, and the elements are entered in random order i.e {4, 6, 1, 2, 5, 3} and the element to be searched is “6”.

```Enter the number of elements 6
Enter the elements one by one
4
6
1
2
5
3
Enter the element to be searched 6
Element is present in the array at position 2```

Test Case 2: In this case, we use the linear search algorithm to find the position of element, and the elements are entered in random order i.e {66, -3, 31} and the element to be searched is “66”.

```Enter the number of elements 3
Enter the elements one by one
66
-3
31
Enter the element to be searched 66
Element is present in the array at position 1```

Test Case 3: In this case, we use the linear search algorithm to find the position of element, and the elements are entered in random order i.e {1, 3, 6, 1, 9} and the element to be searched is “9”.

```Enter the number of elements 5
Enter the elements one by one
1
3
6
1
9
Enter the element to be searched 9
Element is present in the array at position 5```

Method 2: Linear Search in C using Array and Malloc

In this approach, we will find if an element X is present in the array or not and if yes find its position pos using linear search algorithm.

Program/Source Code

Here is source code of the C Program to find the position of an element requested by the user using Linear Search Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

1. `/*`
2. ` * C program to find the pos of element using linear search`
3. ` */`
4. ` `
5. `#include<stdio.h>`
6. `#include<malloc.h>`
7. ` `
8. `int LinearSearch(int *array, int element, int size)`
9. `{`
10. `    int index=0;`
11. `    while (index < size)`
12. `    {`
13. `        if(array[index] == element)`
14. `        {`
15. `            return index;`
16. `        }`
17. `        else`
18. `        {`
19. `            index++;`
20. `        }`
21. `    }`
22. `    return -1;`
23. `}`
24. `int main()`
25. `{`
26. `    int i, size, element;`
27. `    int position;`
28. `    int *array;`
29. `    printf("Enter the Size of the Array:\t");`
30. `    scanf("%d", &size);`
31. `    printf("\n");`
32. ` `
33. `    //allocating the blocks in the memory for array`
34. `    array=(int*)malloc( sizeof (int) * size);`
35. `    if(array==NULL)`
36. `    {`
37. `        printf("Fault Occured in Memory Allocation \n");`
38. `    }`
39. `    else`
40. `    {`
41. `        //Entering the array.`
42. `        printf("Enter the Array:\n");`
43. `        for(i=0;i< size; i++)`
44. `        {`
45. `            printf("arr[%d]=\t",i);`
46. `            scanf("%d", &array[i]);`
47. `        }`
48. ` `
49. `        printf("Enter the Element to be Searched: ");`
50. `        scanf("%d", &element);`
51. `        // Calling the Linear search function`
52. `        position=LinearSearch (array, element, size);`
53. ` `
54. `        if (position != -1)`
55. `        {`
56. `            printf("Element is at %d position from start \t {0-based indexing}\n", position);`
57. `            printf("Element is at %d position from start \t {1-based indexing}\n",position+1);`
58. `        }`
59. `        else`
60. `        {`
61. `            printf("Element not found in the array\n");`
62. `        }`
63. `    }`
64. `}`
Program Explanation

1. First, initialise the variables to store size of the array, pointer to array, temporary variables.
2. Then take the size of the array value as input.
3. Use malloc function to allocate space. If space is allocated, then we proceed further.
4. Then we ask the user for a number to search in the array.
5. Call a Linear Search function passing the arguments such as base address of array, size of the array and element to be found.
6. Then traverse the array to find the array from first element to the last, using a for loop.
7. If any of the elements match, return the index of that element. Else return -1.
8. If the return is -1, it means element is not present in the array.
9. If return != -1, simply print the return value.

Time Complexity:
Average Case: O(n)
As the name suggests it is a linear search and we used a loop to iterate over the array from start to end, hence we can affirm that it is of O(n) complexity, where n = Size of the data structure.

Best Case: O(1)
The best-case complexity will be found if you find the element at the first index from the start *(according to the approach we used). It can be denoted as O(1).

Worst Case: O(n)
If you start traversing from start and get the element at the last index of the array then this will the worst case in terms of time consumption. It can be denoted as O(n), where n = size of array/data structure cardinality.

Space Complexity: O(n + k)
space complexity of the linear search algorithm is O(n + k), where n = size of the array and k = auxiliary variables.

Runtime Test Cases

In this case, we use the linear search algorithm to find the position of element, and the elements are entered in random order i.e {7, 9, 74, 23, 64, 92} and the element to be searched is “74”.

```Enter the Size of the Array: 6
Enter the Array:
arr[0]=	7
arr[1]=	9
arr[2]=	74
arr[3]=	23
arr[4]=	64
arr[5]=	92
Enter the Element to be Searched: 74
Element is at 2 position from start 	 {0-based indexing}
Element is at 3 position from start 	 {1-based indexing}```

Method 3: Linear Search in C using Recursion

In this method, we finds the position of an element in an array using Linear Search Algorithm using Recursion.

Approach:
Linear Search(array, element, start, size of the array)
This is the big problem here as need to search the element in the whole array what if we just solve a small problem where we find if an element is at the Start index. If yes we found the element and return the start as the answer or else we just need to proceed further.

How do we further proceed?

• We must consider the fact that the element will be absent if it is not in an array, or we may state that element is not in the array[start —> size of the array].
• Every time we compare, we reduce the looking area by one, where looking area refers to the size of the array – start.
• In this Linear Search technique, we traverse from the beginning, so start increases by one every time we compare entries.
• We also need to consider a case calling that must stop these cases, which will be as follows.
1. Either we find the element.
2. Or we reached a condition where start == array size, which means we reached the end of the array and the array does not include the element.

Example:

Suppose we have an Array = {1,34,1,78,8,56,21}
And element to be found = 8.

 Linear search(array, 8 , 5, 7) Array[5] == 8 Return 5 Linear search(array, 8 , 4, 7) Array[4] != 8 Linear search(array, 8 , 3, 7) Array[3] != 8 Linear search(array, 8 , 2, 7) Array[2] != 8 Linear search(array, 8 , 1, 7) Array[1] != 8 Linear search(array, 8 , 0, 7) Array[0] != 8 main() ……..arr ={1,34,1,78,8,56,21}……… …….start=0……. ……size of the array=7…. …….Element=8…..
Program/Source Code

Here is the source code of the C Program to implement Linear Search Algorithm on array of numbers using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

1. `/* C Program to implement Linear Search Algorithm recursively */`
2. ` `
3. `#include <stdio.h>`
4. `int RecursiveLS(int arr[], int value, int index, int n)`
5. `{`
6. `    int pos = 0;`
7. ` `
8. `    if(index >= n)`
9. `    {`
10. `        return 0;`
11. `    }`
12. ` `
13. `    else if (arr[index] == value)`
14. `    {`
15. `        pos = index + 1;`
16. `        return pos;`
17. `    }`
18. ` `
19. `    else`
20. `    {`
21. `        return RecursiveLS(arr, value, index+1, n);`
22. `    }`
23. `    return pos;`
24. `}`
25. ` `
26. `int main()`
27. `{`
28. `    int n, value, pos, m = 0, arr[100];`
29. `    printf("Enter the total elements in the array:  ");`
30. `    scanf("%d", &n);`
31. ` `
32. `    printf("Enter the array elements:\n");`
33. `    for (int i = 0; i < n; i++)`
34. `    {`
35. `        scanf("%d", &arr[i]);`
36. `    }`
37. ` `
38. `    printf("Enter the element to search:  ");`
39. `    scanf("%d", &value);`
40. ` `
41. `    pos =  RecursiveLS(arr, value, 0, n);`
42. `    if (pos != 0)`
43. `    {`
44. `        printf("Element found at pos %d ", pos);`
45. `    }`
46. `    else`
47. `    {`
48. `        printf("Element not found");`
49. `    }`
50. `    return 0;`
51. `}`
Program Explanation

1. 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.
2. The array is searched sequentially and the position is returned if the key element to be searched is available in the array, otherwise “Element not found” is printed.
3. Here in this C Program we have created a recursive function called RecursiveLS(), which takes in 4 input parameters and returns the position of element in a array which is searched by the user.
4. If the element that is searched is the first we directly return the index.
5. But if it is not the first element of array, we decrease the size of array by 1, by eliminating the first element of the array, which means when the RecursiveLS() is called second time the array size will be (n-1). This will go on until the element is found.

Linear Search Working Example using Recursion:
……..arr ={1,34,1,78,8,56,21}………
Step 1: Firstly operating system calls the main function of the program.
Then the main function call Linear Search(arr, 8, 1, 7)
Arr[1] = 1
1!=8. The element we are looking for is not at the start, so we need to increase the start and call Linear Search(arr, 8, 1+1, 7)

Step 2: Linear Search(arr, 8, 2, 7)
Arr[2] = 34
34 != 8. The element we are looking for is not at the start, so we need to increase the start and call Linear Search(arr, 8, 2+1, 7)

Step 3: Linear Search(arr, 8, 3, 7)
Arr[3] = 1
1 != 8. The element we are looking for is not at the start, so we need to increase the start and call Linear Search(arr, 8, 3+1, 7)

Step 4: Linear Search(arr, 8, 4, 7)
Arr[4] = 78
78 != 8. The element we are looking for is not at the start, so we need to increase the start and call Linear Search(arr, 8, 4+1, 7)

Step 5: Linear Search(arr, 8, 5, 7)
Arr[5] = 8
8 == 8 hence we need to return value 5. I.e., index of element in array.

This process is known as pop from stack where return to the main function.
Linear Search(arr, 8, 5, 7) returns 5 to Linear Search(arr, 8, 4, 7)
Linear Search(arr, 8, 4, 7) returns 5 to Linear Search(arr, 8, 3, 7)
Linear Search(arr, 8, 3, 7) returns 5 to Linear Search(arr, 8, 2, 7)
Linear Search(arr, 8, 2, 7) returns 5 to Linear Search(arr, 8, 1, 7)
Linear Search(arr, 8, 1, 7) returns 5 to main()
We get our result as 5.

Time Complexity:
Average Case: O(n)
As the name suggests it is a linear search and we used a loop to iterate over the array from start to end, hence we can affirm that it is of O(n) complexity, where n = Size of the data structure.

Best Case: O(1)
The best-case complexity will be found if you find the element at the first index from the start *(according to the approach we used). It can be denoted as O(1).

Worst Case: O(n)
If you start traversing from start and get the element at the last index of the array then this will the worst case in terms of time consumption. It can be denoted as O(n), where n = size of array/data structure cardinality.

Space Complexity: O(n + n’ + k)
space complexity of the linear search algorithm is O(n + k), where n = size of the array, k = auxiliary variables and N’ = memory consumed by the call stack and to store the variables in the call stack.

Runtime Test Cases

In this case, the element to be searched is at random location in the array using linear search.

```Enter the total elements in the array:  7
Enter the array elements:
1
34
1
78
8
56
21
Enter the element to search: 8
Element found at pos: 5```

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.