Linear Search

Linear Search, also known as Sequential Search, is one of the simplest and most intuitive searching algorithms. It involves scanning an array or list of elements one by one until the target element is found or the entire array is traversed. Linear Search is applicable to both sorted and unsorted arrays.

Linear Search Logic

The logic behind Linear Search is straightforward:

1. Start from the first element (index 0) of the array.

2. Compare the current element with the target element.

3. If the current element matches the target element, return its index (position) in the array.

4. If the current element does not match, move to the next element in the array and repeat steps 2 and 3.

5. Continue this process until the target element is found or the end of the array is reached (no match found).

Linear Search in Java:

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // Element found, return its index
            }
        }
        return -1;  // Element not found, return -1
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 8, 6, 1, 9, 5};
        int target = 6;
        int result = linearSearch(arr, target);
        
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result + ".");
        } else {
            System.out.println("Element " + target + " not found in the array.");
        }
    }
}

Linear Search in C:

#include <stdio.h>

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // Element found, return its index
        }
    }
    return -1;  // Element not found, return -1
}

int main() {
    int arr[] = {4, 2, 8, 6, 1, 9, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 6;
    
    int result = linearSearch(arr, size, target);
    
    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }
    
    return 0;
}

Both of these implementations perform a linear search on the given array and return the index of the target element if found, or -1 if the element is not present in the array. You can replace the arr and target values with your own data to test the Linear Search algorithm with different inputs.

Time Complexity

The time complexity of Linear Search can be analyzed mathematically as follows:

Let n be the number of elements in the array.

In the worst-case scenario, Linear Search needs to compare the target element with each element in the array until it either finds a match or reaches the end of the array. Therefore, in the worst case:

• The first comparison takes 1 operation (comparing the target with the first element).

• The second comparison takes 2 operations (comparing the target with the second element).

• The k-th comparison takes k operations.

In the worst case, the target element is either found at the last position in the array or is not present in the array, which means we perform n comparisons.

To calculate the total number of operations (comparisons) in the worst case, we can sum the operations from 1 to n:

$(1 + 2 + 3 + \ldots + n = \frac{n \cdot (n + 1)}{2})$

Therefore, the worst-case time complexity of Linear Search is:

$(T(n) = \frac{n \cdot (n + 1)}{2} = \frac{n^2 + n}{2})$

When we analyze time complexity, we are interested in how the algorithm's performance scales with the size of the input (in this case, the number of elements in the array). In big O notation, we simplify this to:

$(T(n) = O(n^2))$

So, the time complexity of Linear Search is O(n) in the worst case. This means that the number of operations performed by Linear Search grows linearly with the size of the input array. It is a simple but not very efficient searching algorithm, especially for large datasets, where more efficient algorithms like Binary Search or Hashing are preferred.

While Linear Search is not the most efficient algorithm for large datasets, it remains a fundamental concept and serves as the basis for understanding more complex searching algorithms.