Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / c / Solution 2026-10-31
View more
A second binary search locates the first entry strictly greater than x:
def upperBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) <= x) lo = mid + 1
    else hi = mid
  }
  lo
}

def equalRange(a: Array[Int], x: Int): (Int, Int) =
  (lowerBound(a, x), upperBound(a, x))
For upper-bound search, the loop invariant is , , and ; its loop variant is again . The same midpoint and sortedness arguments prove preservation, termination and time complexity. The first binary search in part (b) already has its own loop invariant and loop variant.
Let the two boundaries be . There cannot be a value greater than before the first value at least , so . Every entry between them is simultaneously at least and at most , hence equals . Entries before are smaller and entries at or after are larger, so the interval cannot be extended at either end. This proves the equal-range search result is maximal. If x is absent, i == j, both equal to its insertion position; this can be zero, , or an interior gap. Two logarithmic searches still have logarithmic total time complexity. Computing an upper boundary as lowerBound(a, x+1) would introduce an unnecessary integer overflow bug at the largest integer.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / d / Solution 2026-10-31
View more
Black-box testing chooses inputs and expected outputs from the public specification without using the implementation's control structure. Equivalence class testing partitions the input space into classes expected to exercise similar specified behavior, then chooses representatives; boundary cases test where that behavior changes. For equal-range search, use these concrete representatives:
  • Empty array: ([], 4) gives (0,0).
  • One entry, with the target below, equal, and above it: ([4],3), ([4],4), ([4],5) give (0,0), (0,1), (1,1).
  • An absent interior value: ([1,3,5],4) gives (2,2).
  • One interior match: ([1,3,5],3) gives (1,2).
  • A repeated interior block: ([1,3,3,3,5],3) gives (1,4).
  • A repeated block touching the left or right boundary: ([3,3,5],3) and ([1,3,3],3) give (0,2) and (1,3).
  • Every entry equal: ([3,3,3],3) gives (0,3); targets two and four give (0,0) and (3,3).
  • Extreme keys: ([Int.MinValue,0,Int.MaxValue],Int.MaxValue) gives (2,3), and searching for Int.MinValue gives (0,1).
For each result independently check , the strict inequalities outside the returned interval, and equality inside it. Unsorted inputs violate the precondition; they are not ordinary members of the specified valid-input classes. Software testing supplies evidence about implementations, while the loop invariant proof explains correctness for every valid input.
Read the full article