The Power of Linear Search Algorithm

Introduction

Imagine you have a pile of unsorted books and you're looking for a specific title. How would you find it? You'd probably go through each book one by one until you find the one you're looking for. This is essentially how the Linear Search Algorithm works.

What is Linear Search?

Linear search is a simple method to find a specific item in a list. It works by checking each element of the list, one at a time, until a match is found or the entire list has been searched.

Linear Search in Action

Let's visualize how linear search works.

Linear Search

Linear search works by checking each element in the list one by one until it finds the target.

Let's click on a number from the list below to see how linear search finds it.

You see, it started from the first element and checked each one until it found the target. This takes time, especially if the list is long and the target is at the very end or not present at all.

This is the essence of linear search! It checks every element until the target is found. The time complexity of linear search is O(n), where n is the number of elements in the list.

Algorithm

Now that we understand how linear search works, let's look at the algorithm in detail.

Algorithm

Step 1: Start from the first element of the list.

Step 2: Compare the current element with the target element.

Step 3: If the current element is equal to the target element, then return the index of the current element.

Step 4: Move to the next element in the list.

Step 5: Repeat steps 2 to 4 until the target element is found or the end of the list is reached.

Step 6: If the target element is not found, then return -1.

Pseudocode

The linear search algorithm can be represented in pseudocode as follows:

FUNCTION linear_search(LIST[], TARGET)
    FOR EACH ELEMENT IN LIST DO
        IF ELEMENT == TARGET THEN
            RETURN INDEX OF ELEMENT
        END IF
    END FOR

    RETURN -1
END FUNCTION

Implementation

Now, let's implement the linear search algorithm in various programming languages.

Linear Search Implementation

function linearSearch(list, target) {
    for (let i = 0; i < list.length; i++) {
        if (list[i] === target) {
            return i;
        }
    }
    return -1;
}

let list = [1, 2, 3, 4, 5, 6, 7];
let target = 5;
let index = linearSearch(list, target);
if (index === -1) {
    console.log("Element not found");
} else {
    console.log("Element found at index " + index);
}

function linearSearch($list, $target) {
    for ($i = 0; $i < count($list); $i++) {
        if ($list[$i] === $target) {
            return $i;
        }
    }
    return -1;
}

$list = [1, 2, 3, 4, 5, 6, 7];
$target = 5;
$index = linearSearch($list, $target);
if ($index === -1) {
    echo "Element not found";
} else {
    echo "Element found at index " . $index;
}

def linear_search(list, target):
    for i in range(len(list)):
        if list[i] == target:
            return i
    return -1

list = [1, 2, 3, 4, 5, 6, 7]
target = 5
index = linear_search(list, target)
if index == -1:
    print("Element not found")
else:
    print("Element found at index", index)

public class LinearSearch {
    public static int linearSearch(int[] list, int target) {
        for (int i = 0; i < list.length; i++) {
            if (list[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] list = {1, 2, 3, 4, 5, 6, 7};
        int target = 5;
        int index = linearSearch(list, target);
        if (index == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index " + index);
        }
    }
}

#include <stdio.h>

int linear_search(int list[], int target) {
    for (int i = 0; i < sizeof(list) / sizeof(list[0]); i++) {
        if (list[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5, 6, 7};
    int target = 5;
    int index = linear_search(list, target);
    if (index == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", index);
    }
}

Performance Analysis

The performance of the linear search algorithm can be analyzed in terms of time and space complexity.

The time complexity of linear search is O(n), where n is the number of elements in the list. In the worst-case scenario, the algorithm has to go through each element in the list to find the target.

The space complexity is O(1), as it uses a constant amount of extra space regardless of the size of the list.

Conclusion

Linear search is a simple and intuitive algorithm for finding elements in a list. While it may not be the most efficient algorithm for large datasets, it is easy to understand and implement, making it a valuable tool in certain situations.