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