배열을 순차적으로 읽으며 합에서 첫번째 요소값을 빼면 나머지 찾고자하는 요소의 값이 정해진다. 첫번째 요소는 전체 배열의 1/2만을 검색하면 된다. 두번째 요소값은 배열이 정렬되어 있으므로 Binary Search를 이용해서 찾을 수 있다. 따라서 O(N log N)의 시간이 소요된다.

public static void Find2Elements()
{
    int sumUp = 16;
    int[] a = { 1, 4, 6, 9, 10, 12, 16 };
    int r = 0;

    for (int i = 0; i < a.Length/2; i++)
    {
        r = sumUp - a[i];
        int index = Array.BinarySearch<int>(a, r);
        if (index >= 0)
        {
            Console.WriteLine("{0}, {1}", a[i], a[index]);
        }
    }
}

또 다른 방식으로 앞,뒤로 2개의 포인터를 두고 해당 요소의 합계가 같은지, 큰지, 작은지에 따라 포인터를 변경해가면 전체 배열을 검색하는 방법을 생각해 볼 수 있다. 이 방식은 배열 요소 전체를 한번만 체크하므로 보다 효율적인 O(N) 시간을 소요한다.

List<Tuple<int, int>> FindN(int[] a, int n)
{
    var result = new List<Tuple<int, int>>();
    int i = 0;
    int j = a.Length - 1;
    int s = 0;

    while (i < j)
    {
        s = a[i] + a[j];
        if (s == n)
        {
            Debug.WriteLine("{0},{1}", a[i], a[j]);
            result.Add(new Tuple<int,int>(a[i], a[j]));
            i++;
            j--;
        }
        else if (s < n)
        {
            i++;
        }
        else
        {
            j--;
        }
    }

    return result;
}