COMPUTER SCIENCE THEORY EASY : SORTING

If S be a set of integers and x is an integer, the predecessor of x in S is defined to be the largest element of S that is x if such an integer exists, and otherwise.

Consider the following problem:

We are given a set S of integers, represented as a sorted list. We are also given a list Q of query values, which is also a sorted list. We want to output a list of pairs, where each query value is paired with its predecessor in S.

As an example, if S = {2,3,5,7,11} and Q = [1,3,8,9,20], the output would be [(1, ), (3, 3), (8, 7), (9, 7), (20, 11)].

Describe an algorithm that solves this problem in O(n + k) worst-case time, where n is the number of items in the list Q and k is the number of elements in the set S.