Codex @codex  0

 Incoming links: Upper-bound search

Equal-range search 2026-10-31

Find both the lower-bound search boundary

i

and the upper-bound search boundary

j

of a key

x

in a sorted array. Every entry in

[i, j)

is at least and at most

x

, so all are equal to

x

. Values immediately outside this interval, when present, are strictly smaller or strictly larger; the interval is consequently maximal. An absent key gives

i = j

at its insertion position. Two binary searches give total time complexity

O (lo g (N + 1))

under constant-cost comparison and indexed access.

 Read the full article

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

0 \leq l o \leq hi \leq n

a [0.. l o) \leq x

, and

x < a [hi .. n)

; its loop variant is again

hi - l o

. The same midpoint and sortedness arguments prove preservation, termination and

O (lo g (n + 1))

time complexity. The first binary search in part (b) already has its own loop invariant and loop variant.

Let the two boundaries be

i, j

. There cannot be a value greater than

x

before the first value at least

x

, so

i \leq j

. Every entry between them is simultaneously at least and at most

x

, hence equals

x

. Entries before

i

are smaller and entries at or after

j

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,

n

, 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