Linear Search Algorithm in DSA Typescript

Mental Model

Look at each item one by one until you find the one you want or reach the end.

Analogy: Imagine looking for a book on a shelf by checking each book from left to right until you find it.

Array: [3] -> [7] -> [1] -> [9] -> [5] -> null
Search for: 9
↑ (start here)

Dry Run Walkthrough

Input: array: [3, 7, 1, 9, 5], search value: 9

Goal: Find the position of 9 in the array or say it is not found

Step 1: Check first element 3

[3↑] -> [7] -> [1] -> [9] -> [5] -> null

Why: We start from the first element to see if it matches the search value

Step 2: Check second element 7

[3] -> [7↑] -> [1] -> [9] -> [5] -> null

Why: 3 is not 9, so move to next element

Step 3: Check third element 1

[3] -> [7] -> [1↑] -> [9] -> [5] -> null

Why: 7 is not 9, continue checking next

Step 4: Check fourth element 9

[3] -> [7] -> [1] -> [9↑] -> [5] -> null

Why: Found the search value 9 at this position

Result:

[3] -> [7] -> [1] -> [9↑] -> [5] -> null
Answer: Found 9 at index 3

Annotated Code

DSA Typescript

class LinearSearch {
  static search(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === target) {
        return i; // found target at index i
      }
    }
    return -1; // target not found
  }
}

const array = [3, 7, 1, 9, 5];
const target = 9;
const result = LinearSearch.search(array, target);
if (result !== -1) {
  console.log(`Found ${target} at index ${result}`);
} else {
  console.log(`${target} not found in array`);
}

for (let i = 0; i < arr.length; i++) {

iterate over each element in the array

if (arr[i] === target) {

check if current element matches the target

return i; // found target at index i

stop and return index when target is found

return -1; // target not found

return -1 if target is not in the array after full scan

Output

Found 9 at index 3

Complexity Analysis

Time: O(n) because in the worst case we check every element once

Space: O(1) because we only use a few variables regardless of input size

vs Alternative: Compared to binary search which is O(log n), linear search is slower but works on unsorted arrays

Edge Cases

empty array

returns -1 immediately since there are no elements to check

DSA Typescript

for (let i = 0; i < arr.length; i++) {

target not in array

returns -1 after checking all elements

DSA Typescript

return -1; // target not found

target is first element

returns index 0 immediately

DSA Typescript

if (arr[i] === target) {

When to Use This Pattern

When you need to find an item in a list without any order, use linear search because it checks each item one by one.

Common Mistakes

Mistake: Stopping the search too early without checking all elements
Fix: Only stop when you find the target or finish checking all elements

Mistake: Returning index before confirming the element matches the target
Fix: Always check if arr[i] === target before returning index

Summary

It looks through each item in a list to find a target value.

Use it when the list is unsorted or small.

The key is to check each element one by one until you find the target.

Practice

1. What is the main idea behind the Linear Search Algorithm?

easy

A. Divide the list into halves repeatedly to find the target

B. Check each element one by one until the target is found or list ends

C. Sort the list first then search using binary steps

D. Use a hash table to find the target instantly

Solution

1. Step 1: Understand linear search process

   Linear search checks each element in order, from start to end, to find the target.

2. Step 2: Compare with other search methods

   Binary search divides list, hash uses extra memory, but linear search is simple sequential check.

3. Final Answer:

   Check each element one by one until the target is found or list ends -> Option B

4. Quick Check:

   Linear search = sequential check [OK]

Hint: Linear search means checking items one by one [OK]

Common Mistakes:

• Confusing linear search with binary search
• Thinking linear search requires sorted list
• Assuming linear search is always fastest

2. Which of the following is the correct TypeScript syntax to start a linear search loop over an array arr?

easy

A. for (let i = 0; i < arr.length; i++)

B. for (let i = 1; i <= arr.length; i++)

C. for (let i = 0; i <= arr.length; i++)

D. for (let i = 1; i < arr.length; i++)

Solution

1. Step 1: Identify correct loop start and end

   Array indices start at 0 and go up to length-1, so loop must start at 0 and run while i < length.

2. Step 2: Check each option's loop condition

   for (let i = 0; i < arr.length; i++) uses i=0 and i < arr.length, which is correct. Others either start at 1 or use <= which causes out-of-bounds.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) -> Option A

4. Quick Check:

   Loop from 0 to length-1 [OK]

Hint: Array loops start at 0 and run while less than length [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < causing index errors
• Confusing array length with last index

3. What will be the output of this TypeScript code?

const arr = [4, 7, 1, 9];
const target = 1;
let index = -1;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === target) {
    index = i;
    break;
  }
}
console.log(index);

medium

A. 1

B. -1

C. 2

D. 3

Solution

1. Step 1: Trace the loop and compare elements

   Check arr[0]=4 (not 1), arr[1]=7 (not 1), arr[2]=1 (match found), set index=2 and break loop.

2. Step 2: Output the index variable

   After loop, index is 2, so console.log prints 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Target found at index 2 [OK]

Hint: Stop at first match and print its index [OK]

Common Mistakes:

• Not breaking loop and returning last index
• Confusing index with value
• Assuming index starts at 1

4. Find the error in this linear search code snippet and choose the fix:

const arr = [5, 3, 8];
const target = 3;
let index = -1;
for (let i = 0; i <= arr.length; i++) {
  if (arr[i] === target) {
    index = i;
    break;
  }
}
console.log(index);

medium

A. Change loop condition to i < arr.length

B. Initialize index to 0 instead of -1

C. Remove the break statement

D. Change target to 5

Solution

1. Step 1: Identify loop boundary error

   The loop uses i <= arr.length, which causes i to reach arr.length, an invalid index (out of bounds).

2. Step 2: Fix loop condition to prevent out-of-bounds

   Changing condition to i < arr.length ensures i stays within valid indices 0 to length-1.

3. Final Answer:

   Change loop condition to i < arr.length -> Option A

4. Quick Check:

   Loop must run while i < length [OK]

Hint: Use < not <= for array index loops [OK]

Common Mistakes:

• Using <= causing runtime error
• Changing unrelated variables
• Removing break causing unnecessary iterations

5. You want to find the last occurrence of a target number in an array using linear search. Which modification to this code will achieve that?

const arr = [2, 5, 3, 5, 7];
const target = 5;
let index = -1;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === target) {
    index = i;
    break;
  }
}
console.log(index);

hard

A. Sort the array before searching

B. Add break after setting index to stop at first occurrence

C. Start loop from the end and break at first match

D. Remove the break statement to continue searching all elements

Solution

1. Step 1: Understand current code behavior

   The loop checks all elements; each time target matches, index updates to current i, so last match index remains after loop.

2. Step 2: Identify why removing break helps

   If break was present, loop would stop at first match. Removing break ensures full array is checked for last occurrence.

3. Final Answer:

   Remove the break statement to continue searching all elements -> Option D

4. Quick Check:

   Keep searching to find last occurrence [OK]

Hint: To find last occurrence, check all elements without break [OK]

Common Mistakes:

• Adding break stops search too early
• Sorting changes original order and index meaning
• Starting loop from end requires different logic