Step 4 of 6

Two pointers

On sorted data, two indexes moving toward each other often replace a nested loop. To find a pair summing to a target:

• start with i at the smallest and j at the largest,
• if the sum is too small, the only way to grow it is i++,
• if it's too big, j--.

Each step discards one element for good, so it's O(n) instead of O(n²).

Your turn: write bool pair_sum(const std::vector<int>& sorted, long target) that says whether two different positions hold values summing to target.

Previous: lower_bound and upper_bound Next: Prefix sums