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

Code Explanation

1. linearSearch Function

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
}

• Purpose: This function performs a linear search on an array to find the index of a target element.
• Parameters:
  • int arr[]: The array in which the search is performed.
  • int n: The number of elements in the array.
  • int target: The element to be searched in the array.
• Logic:
  • The function iterates through each element of the array using a for loop.
  • If the current element (arr[i]) matches the target, the function returns the index i.
  • If the loop completes without finding the target, the function returns -1 to indicate that the target is not present in the array.

2. main Function

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;
}

• Purpose: The main function is the entry point of the program. It initializes an array, calls the linearSearch function, and prints the result.
• Steps:

1. Array Initialization:

int arr[] = {2, 7, 9, 11, 13};

An array arr is initialized with 5 integers: {2, 7, 9, 11, 13}.

2. Calculate Array Size:

int n = sizeof(arr) / sizeof(arr[0]);

• sizeof(arr) gives the total size of the array in bytes.
• sizeof(arr[0]) gives the size of one element in the array.
• Dividing the total size by the size of one element gives the number of elements in the array (n = 5 in this case).

3. Target Initialization:

int target = 7;

The target element to be searched is set to 7.

4. Call linearSearch Function:

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

• The linearSearch function is called with the array arr, its size n, and the target 7.
• The function returns the index of the target if found, or -1 if not found.

5. Check and Print Result:

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;
}

• If the index is not -1, it means the target was found, and the program prints the index.
• If the index is -1, it means the target was not found, and the program prints a “not found” message.
• The main function returns 0, indicating successful execution.

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.

• Best Case: O(1)
  • The target element is found at the first position.
• Worst Case: O(n)
  • The target element is at the last position or not present in the array.
• Average Case: O(n)
  • The target element is found somewhere in the middle of the array.