I'm learning algorithms and I'm reading the book "introduction to algorithms 3rd edition", and in a problem section it describes the next problem :
Describe a O(n*log(n))-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
And I don't know if it propose and ordered Set or an unordered Set?
Let x be the sum you want to have. First sort the array. Then for each element in array (a[i]), find if (x-a[i]) exists in the array using binary search.
The pseudo code :
sort(a,n)
for i : 1 to n
if(binary_search(a,i+1,n-1,x-a[i]))
return true
return false
Other method: After sorting, use two pointers first and last to check:
while(first < last) {
if(a[first]+a[last] == x) return true;
else if(a[first]+a[last] < x) first++;
else if(a[first]+a[last] > x) last--;
}
return false;
while(first < last) otherwise you'll return true when x/2 appears in the array.Given a sorted array, you can find if there's a pair that sums to x with with O(n) arithmetic operations.
i := 0
j := len(A) - 1
while i < j {
if A[i] + A[j] < x {
i += 1
} else if A[i] + A[j] == x {
return true
} else if A[i] + A[j] > x {
j -= 1
}
}
return false
Given this, you can determine if any array contains a pair of elements that sums to x using O(n log n) arithmetic operations by sorting the array, and then using the algorithm above.
