07. Linear Search
Search for a specific target value within an unsorted array and return its index.
How It Works & Algorithmic Design
Linear Search inspects elements sequentially from beginning to end:
- Sequential Traversal: Loop over the array using index $i$ from $0$ to $n-1$.
- Match Evaluation: Compare
arr[i] === target. If equal, return index $i$ immediately. - Failure Case: If the iteration reaches the end of the array without a match, return
-1to signal the element was not found.
Why This Approach Works Best
When an array is unsorted, no assumptions can be made about element placement. Every position must be checked in the worst case, making linear search the optimal strategy ($O(n)$ time, $O(1)$ space) without pre-sorting.
Example Walkthrough
Input Array:
[15, 8, 42, 4, 23]Target to search for: 42.
Steps:
arr[0]=15 (No) -> arr[1]=8 (No) -> arr[2]=42 (MATCH!)Finds element at index 2.
Output:
2Index where target is located.
Answer: Linear Search implementation
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}💡 Inspect array elements sequentially and return the matching index.
Key Takeaways
- Linear search works on both sorted and unsorted collections.
- Worst-case performance is $O(n)$ when the target is absent or located at the end.
- Returns index immediately on first match, achieving best-case $O(1)$ runtime.