Linear Search Algorithm in DSA Typescript - Deep Dive

Overview - Linear Search Algorithm

What is it?

Linear search is a simple way to find a value in a list by checking each item one by one from start to end. It stops when it finds the value or reaches the end without finding it. This method works on any list, no matter if it is sorted or not. It is easy to understand and use for small or unsorted lists.

Why it matters

Without linear search, finding an item in a list without order would be very hard or slow. It solves the problem of searching when no special order or structure exists. Many real-life tasks, like looking for a name in a phone book without alphabetical order, rely on this simple method. Without it, we would need complex tools even for simple searches.

Where it fits

Before learning linear search, you should know what lists or arrays are and how to access their items. After mastering linear search, you can learn faster search methods like binary search, which require sorted lists. Linear search is the first step in understanding how searching algorithms work.

Mental Model

Core Idea

Linear search checks each item in order until it finds the target or finishes the list.

Think of it like...

Imagine looking for your favorite book on a messy shelf by checking each book one by one from left to right until you find it or reach the end.

List: [5, 3, 8, 4, 2]
Search for: 4

Start -> 5 (no)
       -> 3 (no)
       -> 8 (no)
       -> 4 (yes, stop)

If not found, reach end and say 'not found'.

Build-Up - 7 Steps

1

Foundation

Understanding Lists and Indexing

Concept: Learn what a list is and how to access items by position.

A list is a collection of items stored in order. Each item has a position called an index, starting from 0. For example, in [10, 20, 30], 10 is at index 0, 20 at index 1, and 30 at index 2. You can get any item by its index.

Result

You can access any item in a list by its index, like list[0] gives the first item.

Understanding indexing is essential because linear search moves through the list using these positions.

2

Foundation

What is Searching in a List?

Concept: Searching means finding if a value exists in a list and where.

When you search for a value, you want to know if it is inside the list and at which position. For example, searching for 20 in [10, 20, 30] returns index 1 because 20 is at position 1.

Result

You can confirm if a value is present and find its location.

Knowing what searching means helps you understand why we need algorithms like linear search.

3

Intermediate

How Linear Search Works Step-by-Step

🤔Before reading on: do you think linear search stops immediately when it finds the target, or does it check all items anyway? Commit to your answer.

Concept: Linear search checks each item in order and stops when it finds the target.

Start at the first item. Compare it with the target value. If it matches, return the index. If not, move to the next item. Repeat until you find the target or reach the end. If not found, return -1 or a 'not found' signal.

Result

The search returns the index of the target if found, or -1 if not.

Knowing that linear search stops early when it finds the target saves time compared to checking everything.

4

Intermediate

Implementing Linear Search in TypeScript

🤔Before reading on: do you think the search should return the index of the first match or all matches? Commit to your answer.

Concept: Write code that loops through the list and compares each item to the target.

function linearSearch(arr: number[], target: number): number { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) { return i; // found target } } return -1; // not found } // Example usage: const numbers = [4, 2, 7, 1, 3]; console.log(linearSearch(numbers, 7)); // Output: 2 console.log(linearSearch(numbers, 5)); // Output: -1

Result

Output: 2 -1

Seeing the code helps connect the idea of checking each item with actual programming.

5

Intermediate

Time Complexity of Linear Search

🤔Before reading on: do you think linear search is faster or slower on larger lists? Commit to your answer.

Concept: Linear search takes longer as the list grows because it may check every item.

If the list has n items, linear search might check all n items in the worst case. This means the time it takes grows linearly with the list size. We say its time complexity is O(n), meaning time grows directly with n.

Result

Linear search is simple but can be slow for big lists.

Understanding time complexity helps you choose the right search method for your needs.

6

Advanced

When Linear Search is the Best Choice

🤔Before reading on: do you think linear search is useful only for small lists or also for unsorted big lists? Commit to your answer.

Concept: Linear search works well when lists are small or unsorted, or when you only need to search once.

If the list is small, the simplicity of linear search beats complex methods. If the list is unsorted and you only search once, sorting first is wasteful, so linear search is better. Also, if the list changes often, linear search avoids the cost of maintaining order.

Result

Linear search remains practical in many real-world cases despite its simplicity.

Knowing when to use linear search prevents unnecessary complexity and wasted effort.

7

Expert

Optimizations and Variations of Linear Search

🤔Before reading on: do you think linear search can be improved to skip some items or run faster? Commit to your answer.

Concept: There are ways to optimize linear search, like sentinel values or searching from both ends.

One optimization is adding a sentinel: place the target at the end temporarily to avoid checking list length each time. Another is bidirectional search: check items from start and end simultaneously to find the target faster. These tricks reduce some overhead but keep the basic linear approach.

Result

Optimized linear search can be slightly faster but still has O(n) time complexity.

Understanding these optimizations reveals how even simple algorithms can be tuned for better performance.

Under the Hood

Linear search works by sequentially accessing each element in the list's memory locations. It compares the stored value with the target value. Because it does not rely on any order, it must check each element until it finds a match or reaches the end. The process uses a simple loop and conditional checks at the machine level.

Why designed this way?

Linear search was designed as the simplest search method requiring no preconditions like sorting. Early computers and programming languages needed a straightforward way to find data in any list. Alternatives like binary search require sorted data, which is not always available or practical. Linear search trades speed for simplicity and universality.

Start
  │
  ▼
[Check item at index 0]──No──▶[Check item at index 1]──No──▶...──No──▶[Check item at index n-1]
  │                                                                                      │
 Yes                                                                                   No
  │                                                                                      │
Return index                                                                         Return -1 (not found)

Myth Busters - 4 Common Misconceptions

Quick: Does linear search require the list to be sorted? Commit to yes or no before reading on.

Common Belief: Linear search only works if the list is sorted.

Reality: Linear search works on any list, sorted or unsorted.

Why it matters: Believing this limits the use of linear search and may cause unnecessary sorting, wasting time.

Quick: Does linear search always check every item even if it finds the target early? Commit to yes or no.

Common Belief: Linear search always checks the entire list regardless of finding the target.

Reality: Linear search stops immediately once it finds the target.

Why it matters: Thinking it always checks all items underestimates its efficiency in best cases.

Quick: Is linear search faster than binary search on large sorted lists? Commit to yes or no.

Common Belief: Linear search is faster than binary search on large sorted lists.

Reality: Binary search is much faster on large sorted lists because it divides the search space.

Why it matters: Using linear search on large sorted data wastes time and resources.

Quick: Can linear search find multiple occurrences of a target in one run? Commit to yes or no.

Common Belief: Linear search always finds all occurrences of the target in one pass.

Reality: Basic linear search stops at the first match; finding all requires modification.

Why it matters: Assuming it finds all matches can cause bugs when multiple targets exist.

Expert Zone

1

Linear search's performance depends heavily on the target's position; early matches save time, late matches cost more.

2

Using sentinel values can reduce boundary checks inside the loop, slightly improving speed in low-level implementations.

3

Bidirectional linear search can halve the average search time by checking from both ends simultaneously.

When NOT to use

Avoid linear search for large sorted lists where binary search or interpolation search is faster. For repeated searches, consider building indexes or hash tables for constant-time lookups.

Production Patterns

Linear search is often used in small datasets, unsorted logs, or when data changes frequently. It is also a fallback method in complex systems when other search structures fail or are unavailable.

Connections

Binary Search Algorithm

Builds-on linear search by requiring sorted data and using divide-and-conquer to speed up search.

Understanding linear search clarifies why binary search needs sorted lists and how it improves efficiency.

Hash Tables

Alternative search method offering faster lookups by using keys instead of scanning lists.

Knowing linear search helps appreciate the speed gains and tradeoffs hash tables provide.

Human Visual Search

Similar process where people scan items one by one to find a target in a cluttered environment.

Recognizing this connection helps understand the natural basis of linear search and its limitations.

Common Pitfalls

#1 Searching for a value but returning true/false instead of the index.

Wrong approach:

function linearSearch(arr: number[], target: number): boolean {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return true;
}
}
return false;
}

Correct approach:

function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}

Root cause:

Confusing the goal of search: finding position vs. just existence.

#2 Not stopping the search after finding the target, causing unnecessary checks.

Wrong approach:

function linearSearch(arr: number[], target: number): number {
let index = -1;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
index = i;
}
}
return index;
}

Correct approach:

function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}

Root cause:

Not using return inside the loop to stop early.

#3 Assuming linear search is efficient for very large sorted lists.

Wrong approach:

// Using linear search on large sorted list
const index = linearSearch(largeSortedArray, target);

Correct approach:

// Use binary search for large sorted list
const index = binarySearch(largeSortedArray, target);

Root cause:

Ignoring time complexity and data properties when choosing search method.

Key Takeaways

Linear search checks each item in order until it finds the target or reaches the end.

It works on any list, sorted or unsorted, making it simple and universal.

Its time grows linearly with list size, so it is slow for large lists.

Stopping early when the target is found saves time in many cases.

Knowing when to use linear search helps avoid unnecessary complexity and inefficiency.