o(nlogn) solution based on binary search below. An o(n) solution based on hashtable is also possible but consume o(n) memory.
public static void main (String[] args) throws java.lang.Exception
{
Pair p = findPairBySum(15, new int[] {1,2,3,4,5,6,7,8,9,10});
System.out.println(p.x);
System.out.println(p.y);
}
public static Pair findPairBySum(int sum, int[] sortedArr)
{
for (int i=0; i= 0)
return new Pair(first, expected);
}
return null;
}
public static int getIndex(int num, int[] sortedArr, int startIndex, int endIndex)
{
if (startIndex > endIndex)
return -1;
int pos = startIndex + (endIndex - startIndex) / 2;
int valAtMiddle = sortedArr[pos];
if (valAtMiddle == num)
return pos;
if (num < valAtMiddle)
return getIndex(num, sortedArr, startIndex, pos-1);
return getIndex(num, sortedArr, pos+1, endIndex);
}
public static class Pair
{
public int x;
public int y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}