finding a pair of integers in a sorted array which sum to K
algorithm, array-algorithms
Solution
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.
Problem
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.