Home / C / Searching / C Program for Linear Search

C Program for Linear Search

in ,
Search

C programs for linear search have been shown here. To find an element in an array using linear search, the program checks each element until the targeted element is found. The following section also covers the algorithm, pseudocode and time complexity of the program.







1. Take input of an array A[] and the size n

2. Take input of the search element S

3. Set i = 0

4. Check if A[i] = S

5. If step 4 is true, display the position i + 1 as output and exit the program.

6. If step 4 is false set i = i + 1

7. If i < n, go to step 4 else exit the program.






Input: An array $A[~]$, size of array $n$ and search element $S$

Output: Position of $S$ in $A[~]$

1. Procedure linearSearch($A[~]$, $n$, $S$):

2. Repeat for $i \in [0, n - 1]$:

3. If $A[i] == S$:

4. Return $i + 1$

5. Return "Element not found"

6. End Procedure






Time Complexity: O(n)

Where n is the total no of elements in the array.





4. C Program for linear search using iteration

Code has been copied
/**********************************************
        	alphabetacoder.com
C program for linear search using iteration
***********************************************/

#include <stdio.h>

int main() {
    // declare an array
    int arr[10] = {12, 20, 23, 4, 9, 13, 1, 32, 5, 19};

    // declare variables
    int i, n, flag = 0;

    // take input from user to search element
    printf("Enter the element to search: ");
    scanf("%d", & n);

    // search the array,
    // if element was found then display the position
    for (i = 0; i < 10; i++) {
        if (arr[i] == n) {
            // display message
            printf("%d has been found at position %d ", n, i + 1);
            // set as found
            flag = 1;
            // break the loop to stop further searching 	
            break;
        }
    }

    // check if not found
    if (flag == 0)
        printf("%d can not be found!", n);

    return 0;
}

Output

Enter the element to search: 13

13 has been found at position 6





5. C Program for linear search using recursion

Code has been copied
/*************************************************
        	alphabetacoder.com
    C program for linear search using recursion
**************************************************/

#include <stdio.h>

// recursive function to perform linear search
// arr[] is the array
// n is the size of array
// s is the search element 
// i is the index of element
int linearSearch(int arr[], int n, int s, int i) {
    // if all the elements have been searched
    if (i == n)
        return -1;

    // if search element has been found return the position
    if (arr[i] == s)
        return (i + 1);
    // if search element has not been found
    // call function to check next element
    else
        linearSearch(arr, n, s, i + 1);
}

int main() {
    // declare an array
    // declare an array
    int arr[10] = {12, 20, 23, 4, 9, 13, 1, 32, 5, 19};

    // declare variables
    int i, s, position;

    // take input from user to search element
    printf("Enter the element to search: ");
    scanf("%d", & s);

    // call function to search element
    // arguments: array, size of array, search element, starting index
    position = linearSearch(arr, 10, s, 0);

    // check if not found
    if (position == -1)
        printf("%d can not be found!", s);
    else
        printf("%d has been found at position %d ", s, position);

    return 0;
}

Output

Enter the element to search: 13

13 has been found at position 6





Labels: ,