Linear Search

Linear search, also known as sequential search, is a method for finding a particular value in a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

Here's an example of a linear search in a list with 10 elements, where we're searching for the value "5":

List:  [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]

Step 1:  [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]  - Check 1, not a match
Step 2:  [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]  - Check 3, not a match
Step 3:  [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]  - Check 5, it's a match!

In this example, each "Step" represents a comparison between the target value (5) and an element in the list. The search stops at Step 3 because it finds the value 5 in the third position of the list. If the value was not in the list, the search would continue until it had checked all 10 elements.

Below is the pseudo-code for a linear search algorithm, assuming you're searching for a specific value in an array or list of numbers.

Algorithm: LinearSearch
Input: A list of elements 'List', the number of elements in the list 'N', and the target value 'Target'
Output: The index of 'Target' in 'List' if found, otherwise -1

Procedure LinearSearch(List, N, Target)
    for index from 0 to N-1
        if List[index] == Target
            return index // Target found
    end for
    return -1 // Target not found
End Procedure

Here's how the algorithm works:

1. Iterate through each element in the list.

2. Compare the current element with the target value.

3. If the current element matches the target, return the current index.

4. If the end of the list is reached and no match is found, return -1 to indicate that the target is not in the list.

Below is a C code implementation of the linear search algorithm, along with explanations for each part:

#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; // Target found, return index
        }
    }
    return -1; // Target not found
}

int main() {
    int array[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0}; // Sample array
    int target = 5; // Target value to search for
    int size = sizeof(array) / sizeof(array[0]); // Calculate the size of the array

    // Perform linear search
    int result = linearSearch(array, size, target);

    // Output 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

1. Include Directive:

   • #include <stdio.h>: This line includes the Standard Input Output header file for basic input/output operations like printf.

2. linearSearch Function:

   • int linearSearch(int arr[], int size, int target): This function performs the linear search. It takes an array arr, its size size, and the target value to search for as arguments.

   • for (int i = 0; i < size; i++): Loop through each element of the array.

   • if (arr[i] == target): Check if the current element equals the target value.

   • return i: If a match is found, return the current index.

   • return -1: If the loop completes without finding the target, return -1, indicating the target is not in the array.

3. main Function:

   • int main(): The main function where the program execution begins.

   • int array[] = {...}: An array of integers is defined and initialized.

   • int target = 5: The target value we are searching for.

   • int size = sizeof(array) / sizeof(array[0]): Determine the size of the array.

   • int result = linearSearch(array, size, target): Call the linearSearch function and store the result.

   • if (result != -1) { ... } else { ... }: Check if the result is -1. If not, the element is found and its index is printed; otherwise, a message is printed indicating that the element is not in the array.

4. Return Statement:

   • return 0: Indicates that the program executed successfully.

Complexity analysis in algorithms typically involves evaluating both time complexity and space complexity. Let's analyze the linear search algorithm in these terms:

Time Complexity

1. Best Case (The target is at the first position):

   • O(1): The algorithm finds the target with the first comparison.

2. Worst Case (The target is not in the array or at the last position):

   • O(n): The algorithm checks each element exactly once, where ( n ) is the number of elements in the array.

3. Average Case:

   • On average, the algorithm will check half of the elements before finding the target or concluding it's not present.

   • O(n/2) which simplifies to O(n): As constants are dropped in Big O notation.

Space Complexity

• O(1): Linear search is an in-place algorithm. It does not require any extra space that scales with input size, as it only uses a few variables for its operation, irrespective of the size of the input array.

Linear search is a simple algorithm with a time complexity of O(n) in the worst and average cases, making it less efficient for large datasets compared to more advanced search algorithms like binary search (which has a time complexity of O(log n)). However, its advantage lies in its simplicity and the fact that it does not require sorted data. The space complexity is O(1), indicating its minimal space requirement.