Lesson 26: Linear Search
Master the fundamental linear search algorithm in JavaScript with interactive examples and step-by-step visualizations.
26.1 Introduction to Linear Search
Linear search, also known as sequential search, is a fundamental algorithm for finding a target value within a list. It sequentially checks each element of the list until a match is found or the entire list has been searched.
Key points: Linear search is simple to implement and works for unsorted data. However, it has a time complexity of O(n), making it inefficient for large datasets compared to binary search (O(log n)).
26.2 How Linear Search Works
The algorithm follows these steps:
- Start from the first element of the array
- Compare the current element with the target value
- If they match, return the current index
- If they don't match, move to the next element
- Repeat steps 2-4 until the element is found or the end of the array is reached
- If the element is not found, return -1
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
26.3 Algorithm Complexity
Best Case
O(1)
Target is first element
Average Case
O(n)
Target in middle
Worst Case
O(n)
Target not present
Space
O(1)
No extra space
Example 26.1: Number Search
Search for a number in an array and visualize the process:
Example 26.2: String Search
Search for a string in an array of names:
Example 26.3: Multiple Occurrences
Find all occurrences of a value in an array:
function linearSearchAll(arr, target) {
const indices = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
indices.push(i);
}
}
return indices;
}
When to use Linear Search:
- When the list is small and unsorted
- When you need to find all occurrences
- When simplicity is more important than efficiency
- As a fallback when other algorithms aren't applicable