Linear

Linear search is a type of sequential searching algorithm. In this method, every element within the input array is traversed and compared with the key element to be found.

If a match is found in the array the search is said to be successful;

if there is no match found the search is said to be unsuccessful and gives the worst-case time complexity.

For instance, in the given animated diagram, we are searching for an element 33.

Therefore, the linear search method searches for it sequentially from the very first element until it finds a match. This returns a successful search.

In the same diagram, if we have to search for an element 46, then it returns an unsuccessful search since 46 is not present in the input.

Linear Search Algorithm

The algorithm for linear search is relatively simple. The procedure starts at the very first index of the input array to be searched.

Step 1 − Start from the 0th index of the input array, compare the key value with the value present in the 0th index.

Step 2 − If the value matches with the key, return the position at which the value was found.

Step 3 − If the value does not match with the key, compare the next element in the array.

Step 4 − Repeat Step 3 until there is a match found. Return the position at which the match was found.

Step 5 − If it is an unsuccessful search, print that the element is not present in the array and exit the program.

pseudocode:

function linear_search(array, target):
    for each item in array:
        if item equals target:
            return item's index
    return "target not found"

Analysis

Linear search traverses through every element sequentially therefore, the best case is when the element is found in the very first iteration.

The best-case time complexity would be O(1).

However, the worst case of the linear search method would be an unsuccessful search that does not find the key value in the array, it performs n iterations.

Therefore, the worst-case time complexity of the linear search algorithm would be O(n).

function linearSearch(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i; // Return the index if the target is found
        }
    }
    return -1; // Return -1 if the target is not found
}

// Example usage:
const arr = [2, 5, 8, 10, 13];
const target = 8;
const result = linearSearch(arr, target);
if (result !== -1) {
    console.log(`Target ${target} found at index ${result}`);
} else {
    console.log(`Target ${target} not found in the array`);
}