= Distinct-index two-sum by suffix lower bounds
For each candidate first index $i$ in a <sorted array>, use <lower-bound search> for $t-a(i)$ only in the suffix starting at $i+1$. A matching result is automatically at a different position. The outer <loop invariant> excludes all solutions whose smaller index precedes $i$; an unsuccessful suffix search extends this exclusion by one. Exhaustion proves absence of any pair. Searching all suffixes gives $O(N\log(N+1))$ <running time> and constant <auxiliary space>. Compute the complement in a sufficiently wide type to avoid <integer overflow> before comparison.
Back to article page
