Linear Search in Javascript

Suppose someone told you to find a specific book on a table. What you will do? In general, you will look forward one by one. When you will find the book before that you will check if the book name match or not. If it does not exist there then you have to check till the end among all the books.

Linear search is a very common search algorithm. indexOf(), includes(), find(), and findIndex() built-in methods behind the scene linear search works.

Linear Search Algorithm

The basic linear search algorithm iterates each element in an array and compares it with the target value. If the target value is found, the index of the element is returned. If the target value is not found, the function returns -1.

The algorithm for linear search is straightforward:

Start at the beginning of the list.
Check each element in the list in order.
If the current element matches the target element, return its index.
If the entire list has been searched and the target element is not found, return -1 to indicate that the target element is not in the list.

Here is the basic implementation of a linear search in JavaScript:

function linearSearch(array, targetElement) {
    for (let i = 0; i < array.length; i++) {
                //checking the targetElement match with the array element
        if (array[i] === targetElement) {
            return `Index ${i} is the position of ${targetElement} `
        }
    }
    return `${targetElement} not found in the array`;
}

In this function, the first parameter is an array to be searched, and the second parameter is the target element. The function iterates through each element in the array and checks if it is equal to the targeted element. If the target value is found, the index of the element is returned. If the target value is not found, the function returns -1. As simple as it is.

Example Usage

Here is an example of how to use the linear search function:

const array = [60, 200, -3, 33, 75];
const targetElement = 200;

console.log(linearSearch(array, targetElement));    //Index 1 is the position of 200

In this example, we have an array of numbers, and we want to find the index of the value 200. We pass the array and the target value to the linear search function, which found the element & returns the index of the target value in the array.

const array = [60, 200, -3, 33, 75];
const targetElement = 2;

console.log(linearSearch(array, targetElement));    //2 not found in the array

In this example, we have an array of numbers, and we want to find the index of the value 2. We pass the array and the target value to the linear search function, which not found the element where checked till the end & returns -1.

Time Complexity of Linear Search

Best-case time complexity of Linear Search

When the targeted value will be at the beginning of the array, then the algorithm will run at constant time, O(1).

Worst-case time complexity of Linear Search

When the targeted value will be at the end of the array, then the algorithm will run at n time, O(n).

Average-case time complexity of Linear Search

When the targeted value will be in the middle of the array, then the algorithm will run at n/2 time, O(n/2) which simplifies to O(n).

Space complexity of Linear Search

Linear Search space complexity is O(1). As it uses no extra space to find the target value.

Conclusion

Linear search is not the most efficient search algorithm, it is straightforward and easy to implement. Now make your hands dirty by coding. Happy coding!

Tanvir Hossain Fahim's Blog