finding a pair of integers in a sorted array which sum to K

Question

Given a sorted array of integers, how can we find a pair of integers that sum to K?

e.g. array = 1,3,5,6,10, K = 6, the answer is 1 and 5.

Time complexity should be minimized.

Answer 1

You may want to look at this blog post:

http://www.codingatwork.com/2011/07/array-sum/

My approach would be to do a binary search of the list for K/2, then walk one variable a left and another variable b right trying to find a solution a+b=K.

The idea would be to start a at the largest number less than or equal to K/2 and start b at the smallest number greater than a. Again, use a binary search to find a and let b be the next element in the array. Then

• If a+b = K, then return (a,b).
• If a+b < K, then move b to the right one position.
• If a+b > K, then move a to the left one position.

Of course, you can skip the binary search and just start a at the beginning of the array and b at the end of the array, and then do

• If a+b = K, then return (a,b).
• If a+b < K, then move a to the right one position.
• If a+b > K, then move b to the left one position.

This is probably faster.