Linear Search

Linear search, also known as sequential search, is a fundamental search algorithm used to find the presence of a specific element within a collection of data. It works by iterating through each element of the data sequentially until the desired element is found or until all elements have been examined.



Algorithm Overview

Linear search is a straightforward and intuitive algorithm that involves a simple step-by-step process:

  1. Start from the beginning of the data collection.
  2. Compare the current element with the target element.
  3. If the current element matches the target, the search is successful, and the algorithm terminates.
  4. If the current element does not match the target, move to the next element in the collection.
  5. Repeat steps 2-4 until the target element is found or until the end of the collection is reached.

Advantages and Use Cases:

Linear search is easy to understand and implement, making it a suitable choice for small datasets or cases where the data is not sorted. It is particularly useful when:

  1. The dataset is small: For small datasets, the difference in efficiency between linear search and more complex algorithms is negligible.
  2. The data is unsorted: Unlike other search algorithms that require sorted data, linear search works on unsorted collections.
  3. Only one occurrence is needed: Linear search is suitable when you only need to find the first occurrence of a target element.

Complexity Analysis

The time complexity of linear search is O(n), where "n" is the number of elements in the collection. In the worst case, the algorithm may need to examine every element in the collection before finding the target or determining its absence. This makes linear search less efficient for large datasets compared to algorithms with better time complexities, such as binary search (O(log n)).

Simple Example

Let's consider an example of searching for a specific number, say 7, in an array of integers: [3, 5, 2, 9, 7, 1, 8]. Starting from the first element, linear search would compare each element with the target, progressing through the array:

  1. Compare 3 (not a match).
  2. Compare 5 (not a match).
  3. Compare 2 (not a match).
  4. Compare 9 (not a match).
  5. Compare 7 (a match). Search successful!

In this case, linear search found the target element (7) in the fifth iteration.

Example in C


Here's an example of an C function that implements the linear search algorithm to find a target element within an array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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 element if found
        }
    }
    return -1; // Return -1 if the target element is not found
}

int main() {
    int arr[] = {3, 5, 2, 9, 7, 1, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

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

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

    return 0;
}

This code defines a linearSearch function that takes an array arr, its size size, and the target element target to search for. It iterates through the array, comparing each element with the target. If the target is found, it returns the index of the target element; otherwise, it returns -1 to indicate that the target is not present in the array.

In the main function, an example array is created, and the linearSearch function is called to search for the target element. The result is then printed to the console.

You can replace the arr, size, and target values in the main function with your own data to perform a linear search on a different array and target element.

Conclusion

Linear search is a basic search algorithm suitable for small datasets and unsorted collections. While it is straightforward to implement and easy to understand, its efficiency decreases for larger datasets due to its linear time complexity. For larger datasets or situations where performance is crucial, more advanced search algorithms, like binary search, offer better efficiency.

   Search this site: