Ternary search whh303 – 1

This note is dedicated to the memory of our teacher E.W. Dijkstra, since he would have appreciated the problem and would probably have solved it nicer than we can do below. Our problem is about three ascending sequences of numbers. It was inspired by [2], exercise C-3.1 (p. 213), which is about two ascending sequences. In order to formulate the problem and its solution, we need some notation on sequences. If s is a sequence of length N, we denote its elements by s.i for 0 ≤ i < N. Sequence s is called ascending iff s.(i − 1) ≤ s.i for all i with 0 < i < N. We write (s|j) to denote the initial segment of s with length j, which consists of the elements s.i with 0 ≤ i < j. Note that s.(j − 1) is the last element of (s|j). Let a, b, c be three ascending sequences of length N. Let abc be the ordered merge of these sequences, which is an ascending sequence of length 3 · N. Given is a natural number m. The aim is to construct an efficient algorithm for the determination of numbers i, j, k such that the ordered merge of (a|i), (b|j