C Linear Search Program


Linear search is a straightforward searching algorithm used to find a specific element in a list or array. The algorithm sequentially checks each element of the list until it finds the target value or reaches the end of the list. This method is simple to implement and works well for small datasets or unsorted arrays.

Key Characteristics of Linear Search

  1. Time Complexity:

    • The worst-case and average-case time complexity of linear search is O(n)O(n), where nn is the number of elements in the array. In the best case, the element is found on the first attempt, leading to a time complexity of O(1)O(1).
  2. Space Complexity:

    • The space complexity of linear search is O(1)O(1) since it uses a constant amount of additional space regardless of the input size.
  3. Use Cases:

    • Linear search is suitable for small or unsorted datasets. It is not efficient for large datasets compared to more advanced algorithms like binary search.

Implementation of Linear Search in C

Below is a simple implementation of the linear search algorithm in C.

#include <stdio.h> // Function to perform linear search int linearSearch(int arr[], int size, int target) { for (int i = 0; i < size; i++) { if (arr[i] == target) { return i; // Return the index of the target if found } } return -1; // Return -1 if the target is not found } int main() { int arr[] = {5, 3, 8, 4, 2}; // Example array int size = sizeof(arr) / sizeof(arr[0]); int target; // Ask user for the target value to search printf("Enter the number to search: "); scanf("%d", &target); // Perform linear search int result = linearSearch(arr, size, target); // Display the result if (result != -1) { printf("Element found at index: %d\n", result); } else { printf("Element not found in the array.\n"); } return 0; }

Explanation of the Code

  1. Header Files:

    • #include <stdio.h>: Includes the standard input-output library for functions like printf and scanf.
  2. Linear Search Function:

    • The function linearSearch takes three parameters:
      • An integer array arr[],
      • An integer size representing the number of elements in the array,
      • An integer target which is the value to search for.
    • The function iterates over each element of the array:
      • If the current element matches the target, it returns the index of that element.
      • If the loop completes without finding the target, it returns -1 indicating that the element is not present in the array.
  3. Main Function:

    • Initializes an example array arr with some integers.
    • Calculates the size of the array using sizeof(arr) / sizeof(arr[0]).
    • Prompts the user to enter a number to search for.
    • Calls the linearSearch function and stores the result.
    • Displays the index of the found element or a message indicating that the element is not found.

How to Run the Program

  1. Compile the Code: Use a C compiler like gcc to compile the code.

    gcc linear_search.c -o linear_search
  2. Execute the Program:

    ./linear_search
  3. Input Data: Enter a number when prompted to see if it exists in the array.

Example Input/Output

Input:

Enter the number to search: 4

Output:

Element found at index: 3

Input:

Enter the number to search: 10

Output:

Element not found in the array.

Conclusion

Linear search is a fundamental algorithm that is easy to understand and implement. It is best used for small or unsorted datasets due to its linear time complexity. While it is not the most efficient searching method for large datasets, it serves as an excellent introduction to search algorithms in programming.