🎓 A1Learner
🔍
0 of 45 lessons completed

Algorithmic Choices

An algorithm is a step-by-step method for solving a problem. The right choice can change how many steps a problem needs.

Linear search checks in order

Linear search walks from the front. This program counts each check while it looks for 40.

@main def main(): Unit =
  val numbers = List(10, 20, 30, 40, 50)
  val target = 40
  var comparisons = 0
  var position = -1
  var index = 0
  while index < numbers.size && position == -1 do
    comparisons = comparisons + 1
    if numbers(index) == target then position = index
    index = index + 1
  println(comparisons)
  println(position)

Binary search halves the range

Binary search checks the middle, then keeps only the half that can hold the target. This program counts each check while it looks for 40.

@main def main(): Unit =
  val numbers = List(10, 20, 30, 40, 50)
  val target = 40
  var comparisons = 0
  var position = -1
  var low = 0
  var high = numbers.size - 1
  while low <= high && position == -1 do
    val middle = (low + high) / 2
    comparisons = comparisons + 1
    if numbers(middle) == target then position = middle
    else if numbers(middle) < target then low = middle + 1
    else high = middle - 1
  println(comparisons)
  println(position)

The gap grows on a longer list

Both searches run on the same ten-item list here. The printed counts show the binary search needing far fewer checks.

@main def main(): Unit =
  val numbers = List(10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
  val target = 100
  var linearCount = 0
  var linearPosition = -1
  var index = 0
  while index < numbers.size && linearPosition == -1 do
    linearCount = linearCount + 1
    if numbers(index) == target then linearPosition = index
    index = index + 1
  var binaryCount = 0
  var binaryPosition = -1
  var low = 0
  var high = numbers.size - 1
  while low <= high && binaryPosition == -1 do
    val middle = (low + high) / 2
    binaryCount = binaryCount + 1
    if numbers(middle) == target then binaryPosition = middle
    else if numbers(middle) < target then low = middle + 1
    else high = middle - 1
  println(linearCount)
  println(binaryCount)
  println(binaryPosition)

Example

@main def main(): Unit =
  val numbers = List(10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
  val target = 70
  var linearCount = 0
  var linearPosition = -1
  var index = 0
  while index < numbers.size && linearPosition == -1 do
    linearCount = linearCount + 1
    if numbers(index) == target then linearPosition = index
    index = index + 1
  var binaryCount = 0
  var binaryPosition = -1
  var low = 0
  var high = numbers.size - 1
  while low <= high && binaryPosition == -1 do
    val middle = (low + high) / 2
    binaryCount = binaryCount + 1
    if numbers(middle) == target then binaryPosition = middle
    else if numbers(middle) < target then low = middle + 1
    else high = middle - 1
  println(linearCount)
  println(binaryCount)
  println(binaryPosition)

Key points

  • Linear search: Checking each item in order finds a value without any order requirement.
  • Binary search: Splitting a sorted list in half again and again finds a value in fewer steps.
  • Comparison: One check of a value against a target counts as a single comparison.
  • Sorted: A list in increasing order is sorted, and binary search needs that order.
  • Choice: The best method depends on the size of the list and whether it is sorted.

In this example, the linear search walks from the front and counts seven checks, then the binary search halves the range and counts four checks, and both agree that 70 sits at position 6.

Note

In Scala, a List is built for head access, so finding a middle item by position costs extra steps.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

Exercise

A sorted list has 1,000 items. Which search needs fewer comparisons?