Algorithms

Linear Search

Linear search checks each element until it finds the target or reaches the end.

target The target value is compared with each array element.
found index The result stays `-1` until a matching element is found.

Linear Search

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

int main(void) {
    int values[5] = {4, 7, 9, 12, 15};
    int target = 12;
    int found = -1;

    for (int i = 0; i < 5; i++) {
        if (values[i] == target) {
            found = i;
            break;
        }
    }

    printf("found=%d\n", found);
    return 0;
}

#include <stdio.h>

int main(void) {
    int values[5] = {4, 7, 9, 12, 15};
    int target = 6;
    int found = -1;

    for (int i = 0; i < 5; i++) {
        if (values[i] == target) {
            found = i;
            break;
        }
    }

    printf("found=%d\n", found);
    return 0;
}

#include <stdio.h>

int main(void) {
    int values[5] = {4, 7, 9, 12, 15};
    int target = 7;
    int found = -1;

    for (int i = 0; i < 5; i++) {
        if (values[i] == target) {
            found = i;
            break;
        }
    }

    printf("found=%d\n", found);
    return 0;
}

  1. values ← ⟨addr A⟩, target ← 12, found ← -1

    3int main(void) {4    int values→ ⟨addr A⟩[5] = {4, 7, 9, 12, 15};5    int target→ 12 = 12; //@target=7, 66    int found→ -1 = -1;

  2. for (int i = 0; i < 5; i++)

    pass 1 of 4
    8for (int i0 = 0; i < 5; i++) {9    if (values[i] == target) {
    All 4 passes — pass 1 is the card above
    passivalues[i]targetfound
    10———
    21———
    32———
    431212-1 → 3

  3. found ← 3

    8for (int i = 0; i < 5; i++) {9    if (values[i]12 == target12) {10        found→ 3 = i3;11        break;12    }

  4. printf("found=%d ", found);

    15    printf("found=%d\n", found3);16    return 0;17}
    outputfound=3

  1. values ← ⟨addr A⟩, target ← 6, found ← -1

    3int main(void) {4    int values→ ⟨addr A⟩[5] = {4, 7, 9, 12, 15};5    int target→ 6 = 6;6    int found→ -1 = -1;

  2. for (int i = 0; i < 5; i++)

    pass 1 of 5
    8for (int i0 = 0; i < 5; i++) {9    if (values[i] == target) {
    All 5 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54

  3. printf("found=%d ", found);

    15    printf("found=%d\n", found-1);16    return 0;17}
    outputfound=-1

  1. values ← ⟨addr A⟩, target ← 7, found ← -1

    3int main(void) {4    int values→ ⟨addr A⟩[5] = {4, 7, 9, 12, 15};5    int target→ 7 = 7;6    int found→ -1 = -1;

  2. for (int i = 0; i < 5; i++)

    pass 1 of 2
    8for (int i0 = 0; i < 5; i++) {9    if (values[i] == target) {

  3. for (int i = 0; i < 5; i++)

    pass 2 of 2
    8for (int i1 = 0; i < 5; i++) {9    if (values[i] == target) {

  4. found ← 1

    8for (int i = 0; i < 5; i++) {9    if (values[i]7 == target7) {10        found→ 1 = i1;11        break;12    }

  5. printf("found=%d ", found);

    15    printf("found=%d\n", found1);16    return 0;17}
    outputfound=1