Linear Search: The Brute Force Approach

Chris is confident after mastering Part 2: Sorting.

"Now I can handle any data!"

But then, he faced an urgent task: finding specific data in the company database.

"Chris, find the user with ID user_9999. The data isn't sorted; it's just piled up."

100,000 mixed-up records. How do you find a specific piece of data here?

There is no special trick. You have no choice but to check them one by one from the beginning to the end.

This is Linear Search, the most intuitive method and the one we use the most.

1. One by One from the Start: The Aesthetics of Simplicity

As the name suggests, Linear Search lines up data like a line and scans it sequentially from start to finish.

It's so simple you might wonder, "Is this even an algorithm?" But 90% of JavaScript's built-in functions use this method.

2. Linear Search inside JavaScript

The array methods we use every day are actually Linear Searches.

const users = ["Alice", "Bob", "Charlie", "Dave", "Eve"];

// 1. indexOf: Returns index if found, -1 if not
users.indexOf("Charlie"); // 2

// 2. includes: Returns true if found, false if not
users.includes("Frank"); // false

// 3. find: Returns the first element that matches the condition (callback)
users.find(user => user.startsWith("D")); // "Dave"

// 4. findIndex: Returns the first index that matches the condition
users.findIndex(user => user === "Eve"); // 4

All these methods internally run a loop from index 0 to length - 1.

3. Implementing It Yourself

Let's implement it simply to understand the principle.

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

linearSearch([10, 50, 30, 70, 80], 30); // 2

4. Performance Analysis: Big-O

The performance of Linear Search is "hit or miss" depending on where the item you are looking for is located.

In other words, if data increases 10-fold, the search time also increases 10-fold.

If the data is not sorted, there is no method other than Linear Search. It is the most honest and certain way.

5. When Should You Use It?

Key Takeaways

"But what if there are 1 million items? To find something at the very back, I have to check 1 million times. That's too slow."

If the data is sorted, we can use a much smarter method.

Let's meet Binary Search, the winning strategy of the Up-Down game that cuts the search space in half with every step.

🔗 References