Linear Search

Time Complexity

Space Complexity

Overview

It's probably the simplest algorithm you'll ever learn and generally doesn't require much explanation (the animation should be enough to understand it) but let's dive into some theory too.

Linear search, also called sequential search, is a basic searching technique used to find a specific element in a list of data items. It operates by inspecting each element in the list one by one until the target element is found or until all elements have been checked.

The process starts at the beginning of the list and moves through each element in a linear fashion, without any jumping or skipping. At each step, the algorithm compares the current element with the target element to see if they match.

If a match is found, the search is successful, and the algorithm returns the position (index) of the target element in the list. However, if the current element does not match the target, the algorithm continues to the next element and repeats the comparison process.

This continues until either the target element is located, in which case the algorithm stops and returns the position, or until the entire list has been examined without finding the target. In the latter case, the algorithm concludes that the element is not present in the list and returns a special indicator (such as -1) to signify the unsuccessful search.

The time complexity of linear search is O(n), meaning the time taken to complete the search grows linearly with the size of the list (n). In the worst-case scenario, when the target element is at the end of the list or not present at all, the algorithm will have to check all elements in the list, resulting in a slower search process for large datasets.

Still, it's a good choice for small data sets where the time inefficiency is not so important. And when thinking about its use cases, brute force PIN password cracking could be considered as one. A hacker basically tries every possible PIN combination until he/she finds the correct one.

Code

def linear_search(arr, target):
    for idx, element in enumerate(arr):
        if element == target:
            return idx
    return -1
 
data = [9, 1, 12, 6, 5, 3, 7]
target_element = 3
result = linear_search(data, target_element)
print("The index of {} is: {}".format(target_element, result))
 
 

function linearSearch(arr, target) {
    for (let idx = 0; idx < arr.length; idx++) {
        if (arr[idx] === target) {
            return idx;
        }
    }
    return -1;
}
 
const data = [9, 1, 12, 6, 5, 3, 7];
const targetElement = 3;
const result = linearSearch(data, targetElement);
console.log(`The index of ${targetElement} is: ${result}`);
 
 

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int idx = 0; idx < arr.length; idx++) {
            if (arr[idx] == target) {
                return idx;
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        int[] data = {9, 1, 12, 6, 5, 3, 7};
        int targetElement = 3;
        int result = linearSearch(data, targetElement);
        System.out.println("The index of " + targetElement + " is: " + result);
    }
}
 

#include <stdio.h>
 
int linearSearch(int arr[], int size, int target) {
    for (int idx = 0; idx < size; idx++) {
        if (arr[idx] == target) {
            return idx;
        }
    }
    return -1;
}
 
int main() {
    int data[] = {9, 1, 12, 6, 5, 3, 7};
    int size = sizeof(data) / sizeof(data[0]);
    int targetElement = 3;
    int result = linearSearch(data, size, targetElement);
    printf("The index of %d is: %d\n", targetElement, result);
    return 0;
}
 

function linearSearch($arr, $target) {
    foreach ($arr as $idx => $element) {
        if ($element === $target) {
            return $idx;
        }
    }
    return -1;
}
 
$data = [9, 1, 12, 6, 5, 3, 7];
$targetElement = 3;
$result = linearSearch($data, $targetElement);
echo "The index of $targetElement is: $result\n";