p1.md

Problem

Describe a 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.

Solution

1. 先檢查集合S是否有排序過
2. 若為沒有排序過的集合，則使用Merge sort先排序過（時間為Merge sort的O(nlogn)
3. 使用以下的演算法（若已排序時間為線性時間O(n)

i ← 1, j ← n
while i < j do
    if S[i] + S[j] = x then
        return true
    if S[i] + S[j] < x then
        i ← i + 1
    else
        j ← j − 1
end
return false