Find two numbers that sum closest to a given number I'm working on the problem of finding 2 numbers that their sum is closest to a specific number. Input numbers are not sorted.

My major idea is to sort the numbers and find from two ends. I'm wondering if there are any better ideas in terms of algorithm time complexity. Any advice of code bug and code style is appreciated.

import sys
def find_closese_sum(numbers, target):
    start = 0
    end = len(numbers) - 1
    result = sys.maxint
    result_tuple = None
    while start &lt; end:
        if numbers[start] + numbers[end] == target:
            print 0, (numbers[start], numbers[end])
            return
        elif numbers[start] + numbers[end] &gt; target:
            if abs(numbers[start] + numbers[end] - target) &lt; result:
                result = abs(numbers[start] + numbers[end] - target)
                result_tuple = (numbers[start], numbers[end])
            end -= 1
        else:
            if abs(numbers[start] + numbers[end] - target) &lt; result:
                result = abs(numbers[start] + numbers[end] - target)
                result_tuple = (numbers[start], numbers[end])
            start += 1

    return result, result_tuple

if __name__ == "__main__":
    numbers = [2,1,4,7,8,10]
    target = 16
    numbers = sorted(numbers)
    print find_closese_sum(numbers, target)
Your approach is good. Improvement you can do is use a better sorting technique and rest the approach you are using seems best one.


Sort all the input numbers (Use better sorting techniques Eg. Quicksort).
Use two index variables l and r to traverse from left and right ends respectively. Initialize l as 0 and r as n-1.
sum = a[l] + a[r]
If sum is less than number, then l++
If sum is greater than number, then r–-.
Keep track of min sum
Repeat steps 3, 4, 5 and 6 while l &lt; r.


Time complexity: complexity of quick sort + complexity of finding the optimum pair 

= O(nlogn) + O(n) = O(nlogn)