 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/imperative-programming/1/d/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-25

For the given sorted array, the complete lower-bound search behavior is

0

for

x \leq 1

1

for

2 \leq x \leq 4

3

for

5 \leq x \leq 10

, and

4

for

x \geq 11

. In particular, 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.

 Read the full article

 New to topics? Read the docs here!