Closest Pair From Sorted List

# 問題

昇順にソートされた配列lstと値xが与えられたとき，和がxに最も近くなる 2 要素のペアをlstから求めよ．

# 答え

原理的には$O(n^2)$で解けるが，lstが昇順にソートされていることをうまく使えば$O(n)$で解ける．

$O(n^2)$

1
2
3
4
5
6
7
8
9
def solve(lst, x):
    diff = 10 ** 9
    ans = (-1, -1)
    for i in range(len(lst)):
        for j in range(i+1, len(lst), 1):
            if abs(x - (lst[i] + lst[j])) < diff:
                diff = abs(x - (lst[i] + lst[j]))
                ans = (lst[i], lst[j])
    return ans

$O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def solve(lst, x):
    diff = 10 ** 9
    ans = (-1, -1)
    low = 0
    high = len(lst) - 1
    while low < high:
        s = lst[low] + lst[high]
        if abs(x - s) < diff:
            ans = (lst[low], lst[high])
            diff = abs(x - s)

        if s < x:
            low += 1
        else:
            high -= 1
    return ans