= Solution
Return the key's active <array index>, or \b[`-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)$.
Back to article page
