## Find pairs of integers in an array that sum to a value

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

My initial thoughts:
For each element $a$ in the array, we can find its complement $s-a$ in the array and output this pair. To speed up the search, we can use binary search. Therefore we need to sort the array first, $O(n\log n)$. Then for each element, we search for its complement, that’s another $O(n\log n)$. Together it’s still $O(n\log n)$.

My initial codes:

```	public static boolean binarySeach(int[] array, int element) {
int low = 0;
int high = array.length;
while (low <= high) {
int mid = low + (high - low) / 2;
if (element < array[mid])
high = mid;
else if (element > array[mid])
low = mid + 1;
else
return true;
}
return false;
}

public static List<Pair<Integer>> findSum(int[] array, int sum) {
Arrays.sort(array);
Set<Integer> visited = new HashSet<Integer>();
for (int i = 0; i < array.length; ++i) {
int a = array[i];
if (!visited.contains(a)) {
int b = sum - a;
if (binarySeach(array, b)) {
}
}
}
return result;
}

Solution:
public static void printPairSums(int[] array, int sum) {
Arrays.sort(array);
int first = 0;
int last = array.length - 1;
while (first < last) {
int s = array[first] + array[last];
if (s == sum) {
System.out.println(array[first] + "" + array[last]);
++first;
--last;
} else {
if (s < sum)
++first;
else
--last;
}
}
}

Comments: the solution utilizes the state of sorted array and does a two-way search. Therefore after sorting, we only need one scan of the array. Altogether it ‘reduces’ the time complexity to $O(n\log n + n)$.

__ATA.cmd.push(function() {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});