= Solution
For the given <sorted array>, the complete <lower-bound search> behavior is $0$ for $x\leq1$, $1$ for $2\leq x\leq4$, $3$ for $5\leq x\leq10$, and $4$ for $x\geq11$. In particular, \b[index $2$ is never the correct answer] because the two equal entries share the same first insertion position.
These <unit tests> cover every value boundary, equality case and missing-value interval:
* Below all entries, including the smallest machine <integer>: `ternarySearch(a, Int.MinValue) == 0` and `ternarySearch(a, 0) == 0`.
* Equality with the first entry: `ternarySearch(a, 1) == 0`.
* Values in the first gap: `ternarySearch(a, 2) == 1` and `ternarySearch(a, 3) == 1`.
* Repeated equality must return the first duplicate: `ternarySearch(a, 4) == 1`.
* Values in the second gap: `ternarySearch(a, 5) == 3` and `ternarySearch(a, 9) == 3`.
* Equality with the final entry: `ternarySearch(a, 10) == 3`.
* Beyond the final entry: `ternarySearch(a, 11) == 4` and `ternarySearch(a, Int.MaxValue) == 4`.
For every tested target, also assert that the <array> is unchanged, the result lies in $[0,4]$, every entry before it is strictly smaller, and every entry from it onward is at least the target. These <postconditions> check the intended partition directly rather than merely accepting any equal occurrence.
Back to article page
