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.scala
Replay: real traced execution (multi-file project)
object Main {
	def linearSearch(arr: Array[Int], target: Int): Int = {
		for (i <- arr.indices) {
			if (arr(i) == target) {
				return i
			}
		}
		-1
	}

	def main(args: Array[String]): Unit = {
		val arr = Array(4, 7, 1, 9, 3, 8)
		val target = 9
		val result = linearSearch(arr, target)
		println(result)
	}
}

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

    11def main(args: Array[String]): Unit = {12	val arr = Array(4, 7, 1, 9, 3, 8)13	val target = 9
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    12val arr = Array(4, 7, 1, 9, 3, 8)13val target = 914val result = linearSearch(arr, target)
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    13val target = 914val result = linearSearch(arr, target)15println(result)
    values this step-1result9target

  4. match ← no

    3for (i <- arr.indices) {4	if (arr(i) == target) {5		return i
    values this stepnomatch0i4arr(i)9target

  5. match ← no

    3for (i <- arr.indices) {4	if (arr(i) == target) {5		return i
    values this stepnomatch1i7arr(i)9target

  6. match ← no

    3for (i <- arr.indices) {4	if (arr(i) == target) {5		return i
    values this stepnomatch2i1arr(i)9target

  7. match ← yes

    3for (i <- arr.indices) {4	if (arr(i) == target) {5		return i
    values this stepyesmatch3i9arr(i)9target

  8. result ← 3

    4if (arr(i) == target) {5	return i6}
    values this step3result3i

  9. stdout ← 3

    14	val result = linearSearch(arr, target)15	println(result)16}
    values this step3stdout3result

Complexity

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

Implementation notes

  • Scala: explicit for (i <- arr.indices) with an early return i the moment arr(i) == target. The stdlib arr.indexOf(target) would hide the walk the lesson is teaching.
  • Method signature def linearSearch(arr: Array[Int], target: Int): Int documents the array contract; the -1 sentinel mirrors the language-neutral spec rather than returning Option[Int].
  • The replay shows the running index, the element being checked, and a match indicator on each frame.