Abhyankar Two Sum Algorithm

We apply partitioning on array a with pivot value t/2 where t is a target integer. After partitioning, right partition will have pairs whose sum is greater than target t. Right partition can have at most one integer from the solution pair if such pair exists. Similarly, right partition will have pairs whose sum is lesser than target t. Left partition can have at most one integer from the solution pair if such a pair exist. If left partition is empty then all pairs have sum greater than target and no solution pair exists. If right partition is empty then all pairs have sum lesser than target and no solution pair exists. In such cases algorithm terminates without further sorting or other computational effort. If both partitions exist then one partition may be smaller than other. In order to reduce sorting effort, algorithm sorts the smaller partition and we apply binary search to find (t-unsorted[j]) where j suggests locations of unsorted array or larger partition. Algorithm assumes distinct integers in the array.

`int partition(int* a, int n, int pivot);

int searchTwoSum(int* sorted, int n, int* unsorted, int m,int t);

bool AbhyankarTwoSum(int* a, int n, int t){
int pivot = t/2;
int q = partition(a,n,pivot);
if(q<(n-q)){ // Left is smaller
if(q==0)
return false; // Left partition empty, fast exit
std::sort(a, a + q); // Sorting smaller partition
return searchTwoSum(a,q,&a[q],n-q,t);
}
else{ // Right smaller
if((n-q)==0)
return false; // Right partition empty, fast exit
std::sort(&a[q],(&a[q]+n-q)); // Sorting smaller partition
return searchTwoSum(&a[q],n-q,a,q,t);
}

int searchTwoSum(int* sorted, int n, int* unsorted, int m,int t){
int j = 0;
while(j<m){
int t1 = t-unsorted[j];
if(std::binary_search(sorted,sorted+n,t1))
return true;
j++;
}
return false;
}

int partition(int* a, int n, int pivot){
int j = 0;
int i = 0;
while(j < n){
if(a[j]<=pivot){
swap(a[i],a[j]);
i++;
}
j++;
}
return i;
}

`