Arrays and Iteration

Linear Search

Inspect each element in order and return the first matching index. If the scan completes without a match, return -1. Demonstrates the early-return pattern and the not-found fall-through.

Algorithm

The canonical found run uses target = 9, which lives at index 3. The spec's second canonical run (target = 2) walks the full array and falls through to -1.

early return Stop scanning the moment a match is found.

Basic Implementation

basic.dart
Replay: real traced execution (multi-file project)
int linearSearch(List<int> arr, int target) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

void main() {
  final arr = <int>[4, 7, 1, 9, 3, 8];
  final target = 9;
  final result = linearSearch(arr, target);
  print(result);
}

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

    10void main() {11  final arr = <int>[4, 7, 1, 9, 3, 8];12  final target = 9;
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    11final arr = <int>[4, 7, 1, 9, 3, 8];12final target = 9;13final result = linearSearch(arr, target);
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    12final target = 9;13final result = linearSearch(arr, target);14print(result);
    values this step-1result9target

  4. match ← no

    2for (var i = 0; i < arr.length; i++) {3  if (arr[i] == target) {4    return i;
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    2for (var i = 0; i < arr.length; i++) {3  if (arr[i] == target) {4    return i;
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    2for (var i = 0; i < arr.length; i++) {3  if (arr[i] == target) {4    return i;
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    2for (var i = 0; i < arr.length; i++) {3  if (arr[i] == target) {4    return i;
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    3if (arr[i] == target) {4  return i;5}
    values this step3result3i

  9. stdout ← 3

    13  final result = linearSearch(arr, target);14  print(result);15}
    values this step3stdout3result

Complexity

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

Implementation notes

  • Dart: write the explicit for (var i = 0; i < arr.length; i++) form and return i; from the helper as soon as the match fires. Calling arr.indexOf(target) would hide the index walk the lesson is teaching.
  • The replay shows i, arr[i], and the boolean match result on every step, matching the lesson spec's state-transition table for the found-case run.