Java two pointers: pair search on sorted input

Java 8+. The program uses only JDK classes and runs without a framework.

Use ordering to justify the movement

A load planner needs two package weights whose sum matches a target. On ascending input, the smallest and largest remaining values define the current pair. If their sum is too small, pairing that left value with any smaller right value cannot reach the target; advancing left discards it safely.

If the sum is too large, pairing the current right value with any larger left value would not help. Decrementing right discards that value. The proof depends on sorted input. Reusing this loop on unsorted arrivals can skip a valid pair even though the code still runs and returns an answer-shaped result.

The sample returns values rather than original indexes. Sorting a copy before calling it would reorder membership and lose the direct relation to original positions unless indexes travel with the values. Decide which result the caller needs before adding a sorting step.

Protect the arithmetic and the input contract

Adding two int values in int arithmetic can overflow and reverse the comparison result. The implementation promotes before addition so its long target is compared with a long sum. It still assumes the input is non-null and sorted; those are documented preconditions, not properties established by the loop.

left must remain less than right so one package position is not used twice. Equal weights at different positions are allowed. An empty or one-element input has no pair. Compare binary search for another algorithm whose speed comes from an input-order precondition.

Working program

import java.util.Arrays;
public class PackagePairSearch {
    static int[] pair(int[] sortedWeights, long target) {
        int left = 0;
        int right = sortedWeights.length - 1;
        while (left < right) {
            long total = (long) sortedWeights[left] + sortedWeights[right];
            if (total == target) return new int[]{sortedWeights[left], sortedWeights[right]};
            if (total < target) left++;
            else right--;
        }
        return new int[0];
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(pair(new int[]{2, 5, 8, 11, 15}, 16)));
        System.out.println(Arrays.toString(pair(new int[]{4}, 8)));
    }
}

Output

[5, 11]
[]

Cost and failure boundaries

Each iteration advances left or retreats right. Neither pointer reverses direction, so there are O(n) iterations and O(1) extra working storage, excluding the tiny returned result. Sorting an unsorted input first adds O(n log n) work and possibly copy storage; include that preprocessing in the caller’s cost.

The first matching pair ends the search. Enumerating every pair or counting duplicate combinations is a different contract that requires handling runs of equal values. Test duplicate weights, negative values, no match, extreme integer endpoints and the one-position case rather than assuming the first working fixture covers them.

Common Mistakes

• Do not use the ordering proof on unsorted input.
• Do not add two int values before promoting the result.
• Do not reuse a single position as both members of a pair.

Connect the contracts

Compare the boundary explained in Sorting costs with the assumptions made by this program.

Compare the boundary explained in Range scans with the assumptions made by this program.