retagged by
396 views
0 votes
0 votes
Can somebody help me out to figure out an algorithm that would work in O(nlogn) for the following problem?

Given a SORTED array of n elements. Find three numbers from the array that will add up to a given number k.

My approach:
Use two pointers that point to first and last elements(say L and H). Add these two elements and subtract it from required value k and store it in a variable, say 'z'. Now binary search for z among the elements between the two pointers. If z is found we have the required 3 numbers. If z is not found, we have to either increment L or decrement H and repeat the process.

So essentially we reduce the size of list by one and perform at most logn comparisons in each iteration, hence O(nlogn)

I can't figure out when to increment L or when to decrement H, in case z is not found. Any ideas?

Thank you
retagged by

1 Answer

0 votes
0 votes

algo : "Use two pointers that point to first and last elements(say L and H).
Add these two elements and subtract it from required value k and store it in a variable, say 'z'.
Now binary search for z among the elements between the two pointers."

Your answer starts here :

If (z==0) return 1;


else if(z>0) {
L++;
return algo;
}

else {
H--;
return algo;
}

Related questions

0 votes
0 votes
1 answer
1
iamdeepakji asked Oct 2, 2018
320 views
What is adaptive algorithm and is merge sort and quick sort is adaptive?
0 votes
0 votes
1 answer
2
saurabh12345 asked Jul 24, 2018
400 views
Insertion sort uses an incremental approach for designing algorithm can someone please explain?
0 votes
0 votes
1 answer
4
Edwees asked Feb 6, 2017
1,890 views
We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks ...