Find Pair With Given Sum in Array

As I’m moving more and more into management I need ways to keep my coding foo fresh so I have taken to solving small problems from various sites on the internet in my spare time. I also miss that feeling of being in the zone and fully engaged in something just difficult enough to stretch myself.

After finding a problem I first attempt the problem without resorting to Google which normaly results in a very naive approach but prepares my mind for learning a better solution. I then revisit the approach and try to improve it by myself, after I have exhausted this I then find ways to improve it from the internet and then implement the Benjamin Franklin Method in order to learn more effectively and prevent just copying and pasting the solution. I then blog about it because the act of writing helps solidify the learning process and clarifys my thoughts.

Problem

Given an unsorted array of integers, find a pair with a given sum in it.

For example

Input:

arr = [8, 7, 2, 5, 3, 1]
sum = 10

Output:

Pair found (8 + 2)

First Attempt

int[] listOfInts = new int[] { 8, 7, 2, 5, 3, 1 };
for (int i = 0; i < listOfInts.Length; i++)
{
    for (int k = 0; k < listOfInts.Length; k++)
    {
        if (i != k && listOfInts[i] + listOfInts[k] == 10)
    {
    Console.WriteLine("Pair found ({0} + {1})", listOfInts[i], listOfInts[k]);
    return;
    }
}
Console.WriteLine("Pair Not Found");
}

The problem with this solution is we are taking a brute force approach by looping through the array twice O(n2) and the space used by the program is O(1).

Second Attempt - Divide and Conquer

If we sort the array and then have two indices at the high and low points we can maintain a search space that allows us to reduce the work needed on each iteration O(n log n) and the space used by the program is O(1).

int[] listOfInts = new int[] { 8, 7, 2, 5, 3, 1 };
Array.Sort(listOfInts);
var low = 0;
var high = listOfInts.Length - 1;
for (int i = 0; i < listOfInts.Length; i++)
{
    if (listOfInts[low] + listOfInts[high] == 10)
    {
        Console.WriteLine("Pair found ({0} + {1})", listOfInts[low], listOfInts[high]);
        return;
    }
    if (listOfInts[low] + listOfInts[high] < 10)
    {
        low++;
    }
    else
    {
        high--;
    }
}
Console.WriteLine("No pair found");