= Solution
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. \b[Total time is $O(n\log n)$], using the paper's unit-cost arithmetic model; doubling large machine integers would require overflow-safe arithmetic.
Back to article page
