Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 5 / c

Sort records (value,original_index) by value using merge sort. For each record with value $a$, run binary search for value $2a$ among the sorted records; return the two retained original indices at the first match, otherwise return nil after all records.

If a valid pair exists, its smaller entry is inspected and the matching doubled entry is found by binary search. Conversely every returned pair satisfies the requested equality. Positivity gives $2a>a$, so the returned entries are distinct even if other entries repeat. Sorting costs $O(n\log n)$, and at most $n$ binary searches cost $O(n\log n)$ altogether. Total time is $O(n\log n)$, using the paper's unit-cost arithmetic model; doubling large machine integers would require overflow-safe arithmetic.