Linear Search

You have an unsorted list. Find whether a given value exists in it. If yes, return its index. If no, return -1.

The only strategy that works on unsorted data is to check every element from left to right until you either find the target or run out of elements. There is no shortcut — you cannot skip an element because you have no information about where the target might be.

Example

Tracing [10, 80, 30, 40, 50], target = 40.

The function starts at index 0. It compares arr[0] with 40. Not a match. It moves to index 1. Compares. Not a match. Continues until it finds the target or exhausts the list.

| 1 | 80 | No | Continue to i=2 | [30, 40, 50] |

| 2 | 30 | No | Continue to i=3 | [40, 50] |

| 3 | 40 | Yes | Return 3 | — |

At i = 3, the function finds that arr[3] equals 40. It stops immediately and returns 3. The remaining elements [50] are never examined.

Each box is one comparison. The flow moves right until a match is found. Linear search can be thought of as a chain: every element is a potential exit point.

If the target had been 99 instead? The scan would visit all 5 elements, each comparison would fail, and the function would return -1. The last element is checked, and no match is found — the loop terminates because the end of the array is reached.

If the array had been empty? The loop would have zero iterations. No comparisons. Return -1 immediately.

Code

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Line by line:

• for i in range(len(arr)): — iterate over every valid index from 0 to len(arr) - 1. The variable i serves double duty: it tracks the current position in the scan, and when a match is found it already holds the correct return value. If the array is empty, range(0) produces no iterations and the loop body never executes.
• if arr[i] == target: — compare the current element with the target. This is the core operation: one comparison per iteration.
• return i — found. Exit immediately. Without this early return, the function would continue scanning even after finding the target — wasting time and returning the last occurrence instead of the first.
• return -1 — the loop completed without finding the target. The value -1 is the conventional sentinel for "not found".

Edge case — target at index 0. The first comparison succeeds, returns 0. Best case: O(1).

Edge case — duplicate values. Returns the index of the first occurrence. To get the last occurrence, reverse the traversal: for i in range(len(arr) - 1, -1, -1):.

Time: O(n) — every element may need to be compared in the worst case. Space: O(1) — a single index variable.

Code Trace

Tracing linear_search([10, 80, 30, 40, 50], 40):

Four iterations for a 5-element list — the target was found before the end. In the worst case (target missing), all 5 elements are compared.

The Sentinel Optimization

Every loop iteration checks two conditions: i < len(arr) (the loop bound) and arr[i] == target (the match check). You can eliminate the bound check by placing the target at the end of the array as a sentinel. The loop is guaranteed to find it, so you only need the match check.

def linear_search_sentinel(arr, target):
    n = len(arr)
    last = arr[n - 1]
    arr[n - 1] = target

    i = 0
    while arr[i] != target:
        i += 1

    arr[n - 1] = last

    if i < n - 1 or last == target:
        return i
    return -1

Line by line:

• n = len(arr) — save the length.
• last = arr[n - 1] — save the original last element. It will be overwritten.
• arr[n - 1] = target — place the target at the last position as sentinel. Now the loop must find it somewhere — either at its real position or at the sentinel position.
• while arr[i] != target: — single condition. No bound check. Python's while loop does not check array bounds — if the sentinel were missing and i exceeded the array length, this would crash. The sentinel guarantees this never happens.
• i += 1 — advance to the next element.
• arr[n - 1] = last — restore the original last element.
• if i < n - 1 or last == target: — if i < n - 1, the target was found before the sentinel position. If last == target, the original last element was the target (it was overwritten and then restored, but we know it matched).
• return i or return -1.

Time: Still O(n), but approximately half the comparisons. Space: O(1).

Linear search is the honest algorithm — no preconditions, no setup. Every other search algorithm trades that flexibility for speed by imposing a constraint (sorted order, a hash function, a tree structure). Knowing when the data is unsorted enough, or the list small enough, that linear search is genuinely the right choice is more useful than memorizing the alternatives.

→ LeetCode 704: Binary Search — compare linear search against binary search on sorted data to see the speed difference.