Pair sum using binary search

#1

#include
#include
#include
using namespace std;
void binary(int a[], int n, int value, int i)
{
int high=n-1, mid, low=0;
while(low<=high)
{
mid=(low+high)/2;
if((value==a[mid]) && (a[i]!=a[mid]))
{
cout << a[i] << " " << a[mid] << " ";
break;
}
else if(value<a[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
}
int main()
{
int n, i, j, sum, k=0, value=0;
cin >> n >> sum;
int a[n];
for(i=0;i<n;i++)
{
cin >> a[i];
}
for(i=0;i<n;i++)
{
value=sum-a[i];
binary(a, n, value, i);
}
return 0;
}

*I’m getting repeated outputs. How should I prevent that?

#2

@Sharleen-Clement-3051084341644767
The approach you are using will ultimately lead to repeated outputs. One way to avoid is the use of a boolean array in which you can mark the indexes you have already used as one. If an index is already used, you shouldnt acknowledge it again. But overall it is not a good approach because you would have to put may checkers which would make the code very complex. If your end goal is to print all the pairs, then a hashmap is the best way to move forward. But if you want to print just a single pair, then a 2 pointer would do the work in O(n) in comparison to your approach which takes O(n*log(n)) time.

If my answer is able to answer your query, please mark the doubt as resolved.

#4

Yes, I’m aware that the two pointer approach is more efficient but I wanted to implement it using binary search!

#5

@Sharleen-Clement-3051084341644767
Yes binary search is also a good approach.