Linear Search

Given an array arr[] and an integer target, return the index of the target element. If the target is not found, return -1. The array is not necessarily sorted.

Linear search is the most fundamental searching algorithm. Since we have no information about the ordering of elements, we must check every element one by one. The key insight is that this is the best we can do for an unsorted array — there is no shortcut below $O(N)$ without additional structure.

1. Iterate through the array using enumerate to get both the index and value.
2. At each position, compare the current element with the target.
3. If they match, immediately return the current index.
4. If the loop completes without finding the target, return -1.

• Returning 0 instead of -1 when the element is not found (0 is a valid index)
• Not handling empty arrays (the loop simply doesn't execute and returns -1 correctly)
• Forgetting to return immediately when the element is found, causing unnecessary iterations

Linear search is simple but important. It establishes the baseline: $O(N)$ for searching an unsorted array. Later, Binary Search achieves $O(\log N)$ — but only on sorted arrays. Understanding this trade-off is fundamental to choosing the right algorithm.