Solution: Binary Search

Notice the brute-force solution can be written like this:

private static int lookup(int[] numbers, int target, int start) {
  for (int i = start; i < numbers.length; i++) {
    if (numbers[i] == target) {
      return i;
    }
  }
  return -1;  // not found
}


public static int[] twoSum(int[] numbers, int target) {
  for (int i = 0; i < numbers.length - 1; i++) {
    int complement = target - numbers[i];
    int j = lookup(numbers, complement, i + 1);
    if (j != -1) {
      return new int[]{i, j};  // Found it!
    }
  }
  return new int[0];  // We never reach here because the problem guarantees a solution exists
}

That is the same algorithm, split into two methods. For each number we compute its complement, which is the number we would have to add to it to reach the target. Then we look for that complement in the positions after index i. lookup is a linear search, so it is $O (n)$ , and we call it about $n$ times, which gives $O (n^{2})$ .

Since the array is sorted, we can make lookup cheaper by using binary search:

private static int lookup(int[] arr, int target, int start) {
  int left = start;
  int right = arr.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;  // Not found
}

public static int[] twoSum(int[] numbers, int target) {
  // Same as before
}

Let’s trace one lookup call. Suppose numbers = [2, 7, 11, 15] and the target is 9. We are at i = 0, so the number is 2 and the complement we want is 7. We search for it in numbers[1..3]. We start with left at index 1 and right at index 3:

┌────┬────┬────┬────┐
│░ 2░│  7 │ 11 │ 15 │
└────┴────┴────┴────┘
        ↑         ↑
        L         R

Index 0 is shaded because it is outside the search window.

The midpoint mid is index 2, whose value is 11. Since 11 > 7, the complement must be to the left, so we move right down to mid - 1:

┌────┬────┬────┬────┐
│░ 2░│  7 │░11░│░15░│
└────┴────┴────┴────┘
        ↑
      L,R

Now the window is just index 1, so L, R, and M all point to the same place. Its value is 7, which is the complement we were looking for, so the search stops here:

┌────┬────┬────┬────┐
│░ 2░│  7 │░11░│░15░│
└────┴────┴────┴────┘
        ↑
      L,R,M

Each comparison cuts the remaining window in half, so the search finds the answer in about $lo g n$ steps instead of scanning every element. So lookup goes from $O (n)$ to $O (lo g n)$ .

We call lookup about $n$ times, and each call is $O (lo g n)$ , so the whole solution is $O (n lo g n)$ . That is faster than $O (n^{2})$ .