Given a sorted array find the pair that forms the sum in O(n) time

This problem is quite frequently asked and we had already seen a solution in O(n) time but using a hash table here. However in this posting we shall see how to attack this problem when the input data is sorted.

For example for the input,

[-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24] and the sum bein 0, the matching pair is -12 and 12

The solution for this problem relies upon the knowledge of the input data : sorted. We will be having two pointers, one from the start of the Array called as min and the other from the end of the array called as max. We always calculate the sum with the values present in the minimum and maximum indexes. If the sum is greater than what is needed, we will be decrementing the max pointer and for the other case, we will be incrementing the min pointer. This happens till min exceeds max.

Following the solution in C++

//============================================================================
// Name        : array_find_sum.cpp
// Author      : Prabhu Jayaraman
// Version     : v1
// Copyright   : Free
// Description : Find elements in the array that equals to given sum
//============================================================================

#include <iostream>
using namespace std;

#define MAX 15

int main()
{
 int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
 const int find_sum = 0;
 int max_index = MAX - 1;
 int min_index = 0;
 while(min_index < max_index)
 {
  if(array[min_index] + array[max_index-min_index] == find_sum)
  {
   cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
   return 0;
  }
  if(array[min_index]+array[max_index-min_index] < find_sum)
  {
   min_index++;
   max_index++;
  }
  if(array[min_index]+array[max_index-min_index] > find_sum)
  {
   max_index--;
  }
 }
 cout << "NO MATCH" << endl;
 return 0;
}
//-12 & 12 matched

Cheers!
Bragaadeesh