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.

Basic Implementation

basic.dart 
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);
}

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.
early return Stop scanning the moment a match is found.