Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 5 / d / Solution

Return the key's active array index, or -1 if absent:

private def isInMap(x: Int): Int = {
  var i = 0
  while (i < used && elements(i) != x) i += 1
  if (i < used) i else -1
}

The loop invariant states that every index below i has a key different from x. The scan ignores all inactive cells, and short-circuit evaluation protects the array access at the end of the active prefix. Key uniqueness makes a successful index unambiguous. Its running time is $O(used)$.