## Wednesday, September 26, 2012

### Find pair of integers sums to x

Given a set of S containing n real numbers, and a real number x. We seek an algorithm to determine whether two elements of S exist whose sum is exactly x
1. Assume that S is unsorted. Give an O(nlogn) algorithm for the problem.
2. Assume that S is sorted. Give an O(n) algorithm for the problem.
For the first case,
1st, sort the set with a O(nlgn) sorting algorithm.
2nd, go through every element in the set, for each element, use binary search to find (x - element) in the set.

For the second case,
1st, find the complementary array, which is subtracted each of array from x.
2nd, it's like walking face to face, and at some point, they will meet each other.

```import java.util.Arrays;

/**
*
*/

/**
* @author antonio081014
* @time: Sep 26, 2012, 11:04:55 AM
*/
public class Main {

public static void main(String[] args) {
Main main = new Main();
main.run();
System.exit(0);
}

public void run() {
int[] array1 = { 1, 3, 5, 9, 8, 4, 2 };
handleUnsorted(array1, 7);

int[] array2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
handleSorted(array2, 10);
}

public void handleUnsorted(int[] array, int x) {
Arrays.sort(array); // O(nlgn);
for (int i = 0; i < array.length; i++) { // O(n);
int found = x - array[i];
int low = 0;
int high = array.length - 1;
while (low <= high) {// O(lgn);
int mid = (low + high) / 2;
if (mid != i && array[mid] == found) {
System.out.println("Found it: " + array[i] + ", "
+ array[mid]);
return;
} else if (array[mid] < found)
low = mid + 1;
else
high = mid - 1;
}
} // O(nlgn);
}

public void handleSorted(int[] array, int x) {
int n = array.length;
int[] implementArray = new int[n];
for (int i = 0; i < n; i++)
implementArray[i] = x - array[i];
for (int i = 0, j = 0; i < n && j < n;) { // O(n);
if (implementArray[j] == array[i] && i != j) {
// avoid using one elements twice.
System.out.println("Found it: " + (x - array[i]) + ", "
+ implementArray[j]);
return;
} else {
if (array[i] < implementArray[j])
i++;
else
j++;
}
}
}
}
```