Arrays and Iteration

Linear Search

Walk an array once looking for a target value. Return the index of the first match, or -1 if none. The simplest possible search loop.

Algorithm

Canonical input arr = [4, 7, 1, 9, 3, 8] with target = 9 finishes after four compares; the matching index is 3.

early exit Return the index the moment `arr[i]` equals the target. Walking past it would defeat the point.
sentinel return A no-match walk falls off the loop and returns `-1`.

Basic Implementation

basic.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int linearSearch(const int *arr, size_t n, int target) {
    for (size_t i = 0; i < n; ++i) {
        if (arr[i] == target) {
            return (int)i;
        }
    }
    return -1;
}

int main(void) {
    int arr[] = {4, 7, 1, 9, 3, 8};
    size_t n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int result = linearSearch(arr, n, target);
    printf("%d\n", result);
    return 0;
}

  1. arr ← [4, 7, 1, 9, 3, 8]

    12int main(void) {13    int arr[] = {4, 7, 1, 9, 3, 8};14    size_t n = sizeof(arr) / sizeof(arr[0]);
    values this step[4, 7, 1, 9, 3, 8]arr

  2. n ← 6

    13int arr[] = {4, 7, 1, 9, 3, 8};14size_t n = sizeof(arr) / sizeof(arr[0]);15int target = 9;
    values this step6n[4, 7, 1, 9, 3, 8]arr

  3. target ← 9

    14size_t n = sizeof(arr) / sizeof(arr[0]);15int target = 9;16int result = linearSearch(arr, n, target);
    values this step9target6n

  4. result ← -1

    15int target = 9;16int result = linearSearch(arr, n, target);17printf("%d\n", result);
    values this step-1result9target

  5. match ← no

    4for (size_t i = 0; i < n; ++i) {5    if (arr[i] == target) {6        return (int)i;
    values this stepnomatch0i4arr[i]9target

  6. match ← no

    4for (size_t i = 0; i < n; ++i) {5    if (arr[i] == target) {6        return (int)i;
    values this stepnomatch1i7arr[i]9target

  7. match ← no

    4for (size_t i = 0; i < n; ++i) {5    if (arr[i] == target) {6        return (int)i;
    values this stepnomatch2i1arr[i]9target

  8. match ← yes

    4for (size_t i = 0; i < n; ++i) {5    if (arr[i] == target) {6        return (int)i;
    values this stepyesmatch3i9arr[i]9target

  9. result ← 3

    5if (arr[i] == target) {6    return (int)i;7}
    values this step3result3i

  10. stdout ← 3

    16int result = linearSearch(arr, n, target);17printf("%d\n", result);18return 0;
    values this step3stdout3result

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • C: explicit for (size_t i = 0; i < n; ++i). C has no find helper — the lesson is teaching the walk directly.
  • Function signature int linearSearch(const int *arr, size_t n, int target) documents the integer-array contract; the (int)i cast makes the size/index sign discipline explicit.
  • The replay shows the running index, the element being checked, and a match indicator on each frame.