Linear Search

Linear search

Linear search is a straightforward searching algorithm that sequentially checks each element in a list or array until a match is found or until all the elements have been checked.

Here’s how the linear search algorithm works:

1. Start from the beginning of the array: Begin searching from the first element of the array.
2. Compare the target element: Compare the target element with the current element being examined.
3. Iterate through the array: If the current element matches the target element, return its index. If not, move to the next element.
4. End of the array or element found: If the end of the array is reached without finding the target element, return a special value (e.g., -1) to indicate that the element is not in the array.

Here’s a simple implementation of linear search in C:

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Return the index of the target element if found
        }
    }
    return -1; // Return -1 if the target element is not found
}

int main() {
    int arr[] = {2, 7, 9, 11, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int index = linearSearch(arr, n, target);

    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found in the array\n", target);
    }

    return 0;
}

Output:

Value 7 found at index 1

Time Complexity

The time complexity of linear search is O(n), where n is the number of elements in the array or list being searched.

Here’s why the time complexity is O(n):

• In the worst-case scenario, the linear search algorithm might need to iterate through the entire array or list to find the target element.
• The algorithm does not rely on any assumptions about the data being searched, such as the data being sorted.
• It sequentially compares each element of the array or list with the target element until a match is found or until all elements have been examined.

Because the algorithm’s time to completion increases linearly with the number of elements in the array or list, its time complexity is O(n).