What is Linear Search?

Linear Search is a simple searching algorithm used to find the presence of a target element in a given list or array. The algorithm sequentially checks each element of the list until it finds the target element or reaches the end of the list. Linear Search is one of the most straightforward and easy-to-understand search algorithms, but it is not the most efficient when dealing with large datasets.

How Linear Search Works ?

The Linear Search algorithm compares the target element with each element of the array or list one by one until it either finds the target element or determines that the target is not present.

Step-by-step explanation:

1. Start at the first element of the array.
2. Compare the current element with the target value.
3. If the current element matches the target, return the index of the element.
4. If the current element does not match the target, move to the next element.
5. Repeat this process until either the element is found or the end of the array is reached.

Example of Linear Search

Let’s take an example of searching for the value 22 in the array [10, 20, 30, 22, 50]:

1. Initial List: [10, 20, 30, 22, 50]
2. Target Element: 22

Steps:

• Compare 10 with 22 → No match.
• Compare 20 with 22 → No match.
• Compare 30 with 22 → No match.
• Compare 22 with 22 → Match found.

The target element 22 is found at index 3.

C++ Program to search an element in an array using Linear Search Algorithm

#include <iostream>
using namespace std;

// Function to perform linear search
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        // Check if the current element matches the target
        if (arr[i] == target) {
            return i;  // Return the index if target is found
        }
    }
    return -1;  // Return -1 if the target is not found
}

// Main function
int main() {
    int arr[] = {10, 20, 30, 22, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 22;

    int result = linearSearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found in the array." << endl;
    }

    return 0;
}

Java Program to search an element in an array using Linear Search Algorithm

public class Main {
    // Function to perform linear search
    public static int linearSearch(int arr[], int target) {
        for (int i = 0; i < arr.length; i++) {
            // Check if the current element matches the target
            if (arr[i] == target) {
                return i;  // Return the index if target is found
            }
        }
        return -1;  // Return -1 if the target is not found
    }

    // Main function
    public static void main(String[] args) {
        int arr[] = {10, 20, 30, 22, 50};
        int target = 22;

        int result = linearSearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Python Program to search an element in an array using Linear Search Algorithm

# Function to perform linear search
def linear_search(arr, target):
    # Traverse through all elements in the array
    for i in range(len(arr)):
        # Check if the current element matches the target
        if arr[i] == target:
            return i  # Return the index if target is found
    return -1  # Return -1 if the target is not found

# Main function
if __name__ == "__main__":
    arr = [10, 20, 30, 22, 50]
    target = 22

    result = linear_search(arr, target)
    if result != -1:
        print(f"Element found at index: {result}")
    else:
        print("Element not found in the array.")

Properties of Linear Search

• Time Complexity:
  • Best Case: O(1) - when the target element is the first element of the array.
  • Average Case: O(n)
  • Worst Case: O(n) - when the target element is at the end of the array or not present.
• Space Complexity: O(1) - Linear Search does not require any additional memory beyond the input array.
• Stability: Linear Search is stable because it maintains the order of elements.
• Adaptability: Linear Search is adaptable in that it does not require the array to be sorted.

When to Use Linear Search ?

Linear Search is useful in scenarios where:

• The dataset is small or unsorted.
• You need a simple and easy-to-implement algorithm.
• You want to search in linked lists, where binary search is not applicable.

Linear Search is not efficient for large datasets, as it requires checking each element one by one. For large datasets, more advanced search algorithms like Binary Search should be used, especially if the data is sorted.