Linear Search

Linear search checks array elements one at a time until it finds the target or reaches the end of the array. It is useful for unsorted data.

JavaScript search methods

Many built-in JavaScript methods perform a linear search under the hood:

Implementing linear search

The function below returns the index of the target. If the target is not found, it returns -1.

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

  return -1;
}

The loop stops as soon as it finds a match. Otherwise, it checks every element and then returns -1.

Examples

Basic usage

const numbers = [10, 15, 20, 25, 30];

console.log(linearSearch(numbers, 15)); // 1
console.log(linearSearch(numbers, 30)); // 4
console.log(linearSearch(numbers, 99)); // -1 (not found)

const fruits = ["apple", "banana", "cherry", "mango"];

console.log(linearSearch(fruits, "cherry")); // 2
console.log(linearSearch(fruits, "grape"));  // -1

Time complexity

For an unsorted array, the number of checks depends on where the target appears:

Key Takeaways

• Sequential Inspection: Linear search inspects elements sequentially one by one from beginning to end until the target is found or the array ends.
• Works on Unsorted Data: Unlike binary search, linear search does not require the input array to be sorted.
• Time Complexity: Best case is $O(1)$ when the target is at index 0. Average and worst cases are $O(n)$ when the target is near the end or absent.
• Space Complexity: Operates in $O(1)$ constant auxiliary space because it only requires an index counter to traverse the array.
• Built-in Methods: Common JavaScript methods like indexOf, includes, find, and findIndex perform a linear search under the hood.