Loading learning content...
In the previous section, we built intuition for what linear search does. Now, we transform that intuition into precision—the exact, unambiguous steps that define the algorithm.
This transformation from 'I understand it' to 'I can specify it exactly' is a fundamental skill in algorithm design. Computers require perfect precision; they cannot fill in gaps or infer intent. A robust algorithm specification leaves nothing to interpretation.
We'll approach this rigorously: first defining the algorithm in pseudocode, then implementing it in multiple languages, tracing through concrete examples, and finally examining the invariants and correctness properties that guarantee the algorithm works.
By the end of this page, you will be able to write linear search from scratch in any programming language, trace its execution step-by-step, identify the loop invariants that guarantee correctness, and recognize the subtle edge cases that trip up careless implementations.
Pseudocode provides a language-agnostic specification of an algorithm. It's precise enough to implement but abstract enough to transcend any particular programming language's syntax.
Linear Search — Find First Occurrence:
1234567891011
ALGORITHM LinearSearch(A, n, target) // Input: Array A of n elements, target value to find // Output: Index of first occurrence of target, or -1 if not found FOR i ← 0 TO n - 1 DO IF A[i] = target THEN RETURN i // Found: return index immediately END IF END FOR RETURN -1 // Not found: exhausted all elementsBreaking Down Each Component:
Line 1: Function Signature
A — The array (or collection) to search throughn — The number of elements in A (could be inferred from A in many languages)target — The value we're searching forLine 5: The Loop
FOR i ← 0 TO n - 1 — We iterate through every valid indexLines 6-8: The Comparison
IF A[i] = target — The core operation: does this element match?RETURN i — Early termination: we exit immediately upon finding a matchLine 11: The Failure Case
RETURN -1 — A sentinel value indicating "not found"null, throw an exception, return a tuple (found, index)The -1 convention comes from early C programming, where functions returned a single integer. Since valid indices are non-negative, -1 was a natural choice for signaling failure. Modern languages often prefer Optional/Maybe types, exceptions, or explicit result objects—but the -1 convention remains ubiquitous in algorithm textbooks and competitive programming.
Let's implement linear search in several popular programming languages. You'll notice that despite syntactic differences, the core structure remains identical—a testament to how fundamental this algorithm is.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
def linear_search(arr: list, target) -> int: """ Search for target in arr using linear search. Args: arr: List of elements to search through target: Value to find Returns: Index of first occurrence of target, or -1 if not found Time Complexity: O(n) where n = len(arr) Space Complexity: O(1) - only uses constant extra space """ for i in range(len(arr)): if arr[i] == target: return i return -1 # Pythonic alternative using enumeratedef linear_search_pythonic(arr: list, target) -> int: """More Pythonic version using enumerate.""" for index, element in enumerate(arr): if element == target: return index return -1 # Using built-in (for reference, not manual implementation)def linear_search_builtin(arr: list, target) -> int: """Using Python's built-in index method (with error handling).""" try: return arr.index(target) # This uses linear search internally except ValueError: return -1 # Example usageif __name__ == "__main__": test_array = [64, 34, 25, 12, 22, 11, 90] target = 22 result = linear_search(test_array, target) if result != -1: print(f"Element {target} found at index {result}") else: print(f"Element {target} not found")Despite four different languages with different paradigms (interpreted vs compiled, dynamic vs static typing), the core algorithm structure is identical: a loop from 0 to n-1, a comparison check, early return on match, -1 on failure. This structural invariance is a hallmark of fundamental algorithms—they transcend language syntax.
To build deep understanding, let's trace through linear search execution with a concrete example. This mechanical stepping through is essential for debugging and for truly understanding what the algorithm does.
Example: Search for target 22 in array [64, 34, 25, 12, 22, 11, 90]
| Iteration | i | arr[i] | arr[i] == 22? | Action |
|---|---|---|---|---|
| 1 | 0 | 64 | 64 ≠ 22 → false | Continue to next iteration |
| 2 | 1 | 34 | 34 ≠ 22 → false | Continue to next iteration |
| 3 | 2 | 25 | 25 ≠ 22 → false | Continue to next iteration |
| 4 | 3 | 12 | 12 ≠ 22 → false | Continue to next iteration |
| 5 | 4 | 22 | 22 = 22 → true | RETURN 4 (found!) |
Key Observations:
11 and 90) were never examinedNow let's trace a failure case—searching for 100 which doesn't exist:
| Iteration | i | arr[i] | arr[i] == 100? | Action |
|---|---|---|---|---|
| 1 | 0 | 64 | 64 ≠ 100 → false | Continue |
| 2 | 1 | 34 | 34 ≠ 100 → false | Continue |
| 3 | 2 | 25 | 25 ≠ 100 → false | Continue |
| 4 | 3 | 12 | 12 ≠ 100 → false | Continue |
| 5 | 4 | 22 | 22 ≠ 100 → false | Continue |
| 6 | 5 | 11 | 11 ≠ 100 → false | Continue |
| 7 | 6 | 90 | 90 ≠ 100 → false | Continue |
| (exit) | 7 | — | i = n, loop ends | RETURN -1 (not found) |
When the element is not found, we must examine every single element before we can conclude it's absent. This is the worst-case scenario: n comparisons for an n-element array. There's no shortcut—certainty of absence requires exhaustive checking.
For simple algorithms, correctness seems obvious. But proving correctness rigorously requires identifying loop invariants—conditions that remain true before, during, and after each iteration.
What is a Loop Invariant?
A loop invariant is a property that:
The Loop Invariant for Linear Search:
Invariant: At the start of iteration i, the target is NOT in A[0..i-1].
In other words: every element we've already examined does not contain the target. If it did, we would have already returned. This invariant guarantees that when the loop ends, we've verified the target isn't in any examined portion.
Proof of Correctness:
Initialization: Before the first iteration (i = 0), the range A[0..-1] is empty. An empty range trivially doesn't contain the target. ✓
Maintenance: Assume the invariant holds at the start of iteration i (target not in A[0..i-1]). In iteration i:
A[i] = target, we return i immediately—the algorithm terminates correctly.A[i] ≠ target, we proceed to iteration i+1. Now target is not in A[0..i], so the invariant holds for i+1. ✓Termination: The loop terminates in one of two ways:
A[i] = target. Correct.A[0..n-1]—the entire array. We correctly return -1. ✓Why This Matters:
This formal reasoning may seem excessive for linear search, but the skill transfers directly to more complex algorithms. Binary search, for example, has much subtler invariants, and getting them wrong leads to off-by-one errors. Practice reasoning about invariants on simple algorithms to build the muscle for complex ones.
Even the simplest algorithms have edge cases that must be handled correctly. Identifying and testing edge cases is a professional skill that separates robust implementations from fragile ones.
Critical Edge Cases for Linear Search:
| Edge Case | Input | Expected Output | Why It Matters |
|---|---|---|---|
| Empty array | [], target=5 | -1 | No elements to search; must not crash |
| Single element (found) | [5], target=5 | 0 | Minimal positive case |
| Single element (not found) | [3], target=5 | -1 | Minimal negative case |
| Target at first position | [5,3,7], target=5 | 0 | Best case; tests early termination |
| Target at last position | [3,7,5], target=5 | 2 | Worst case for found; tests full scan |
| Multiple occurrences | [5,3,5,5], target=5 | 0 | Should return FIRST occurrence |
| All elements are target | [5,5,5,5], target=5 | 0 | Degenerate case; first is returned |
| Large array, not found | [1..1000000], target=-1 | -1 | Performance test; all elements examined |
| Null/undefined handling | null, target=5 | Error or -1 | Language-dependent; handle gracefully |
Defensive Implementation:
A production-quality implementation should handle these cases gracefully. Here's a defensive Python implementation:
12345678910111213141516171819202122232425262728293031323334353637383940
def linear_search_defensive(arr, target): """ Defensive linear search implementation. Handles: - None/null array - Empty array - All standard cases Returns: int: Index of first occurrence, or -1 if not found/invalid input """ # Guard clause: handle null/None input if arr is None: return -1 # Guard clause: handle non-iterable input if not hasattr(arr, '__iter__'): raise TypeError("Input must be iterable") # Standard linear search (works for empty array too) for i, element in enumerate(arr): if element == target: return i return -1 # Comprehensive test suitedef test_linear_search(): assert linear_search_defensive([], 5) == -1, "Empty array" assert linear_search_defensive([5], 5) == 0, "Single element found" assert linear_search_defensive([3], 5) == -1, "Single element not found" assert linear_search_defensive([5, 3, 7], 5) == 0, "Target at first" assert linear_search_defensive([3, 7, 5], 5) == 2, "Target at last" assert linear_search_defensive([5, 3, 5, 5], 5) == 0, "Multiple occurrences" assert linear_search_defensive(None, 5) == -1, "None input" print("All tests passed!") test_linear_search()Before implementing any algorithm, list the edge cases first. Then write tests for them. Finally, implement the algorithm. This test-driven approach catches subtle bugs that manual testing often misses, and it forces you to understand the problem deeply before writing code.
The basic linear search finds the first occurrence. But real-world scenarios often require variations. Let's implement the most common ones:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
# VARIANT 1: Find Last Occurrencedef linear_search_last(arr, target): """Return index of LAST occurrence of target, or -1 if not found.""" result = -1 for i, element in enumerate(arr): if element == target: result = i # Update result, don't return yet return result # VARIANT 2: Find All Occurrencesdef linear_search_all(arr, target): """Return list of ALL indices where target occurs.""" indices = [] for i, element in enumerate(arr): if element == target: indices.append(i) return indices # VARIANT 3: Count Occurrencesdef linear_search_count(arr, target): """Return count of how many times target appears.""" count = 0 for element in arr: if element == target: count += 1 return count # VARIANT 4: Find with Predicate (Generalized Search)def linear_search_predicate(arr, predicate): """Return index of first element where predicate(element) is True.""" for i, element in enumerate(arr): if predicate(element): return i return -1 # VARIANT 5: Find Minimum/Maximum Elementdef linear_search_min(arr): """Return index of minimum element, or -1 for empty array.""" if not arr: return -1 min_idx = 0 for i in range(1, len(arr)): if arr[i] < arr[min_idx]: min_idx = i return min_idx # Usage examplesarr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] print(f"First 5: {linear_search_first(arr, 5)}") # 4print(f"Last 5: {linear_search_last(arr, 5)}") # 10print(f"All 5s: {linear_search_all(arr, 5)}") # [4, 8, 10]print(f"Count 5s: {linear_search_count(arr, 5)}") # 3print(f"First > 6: {linear_search_predicate(arr, lambda x: x > 6)}") # 5print(f"Min index: {linear_search_min(arr)}") # 1Key Differences in Variants:
| Variant | Early Termination? | Tracks State? | Return Type |
|---|---|---|---|
| Find First | Yes | No | Single index |
| Find Last | No (must scan all) | Yes (last match) | Single index |
| Find All | No (must scan all) | Yes (list of matches) | List of indices |
| Count | No (must scan all) | Yes (count) | Integer |
| Predicate | Yes | No | Single index |
Notice that Find First and Predicate Search can terminate early, while the others must examine every element. This has implications for performance when the data has specific characteristics.
We've transformed linear search from intuition to precise, implementable algorithm. Let's consolidate:
What's Next:
With the mechanics mastered, we turn to performance analysis. The next page provides a rigorous examination of linear search's time complexity: why it's O(n), what that means in practice, how best/average/worst cases differ, and how to reason about performance as data scales.
You can now implement linear search from scratch in any language, trace its execution step-by-step, prove its correctness using loop invariants, identify edge cases, and implement common variants. Next, we dive into complexity analysis.