bisect_left による最近傍探索

bisect_left(a, x) が返すのは「ソート順を保ったまま x を挿入できる位置」であって、x に最も近い要素の位置ではありません。返り値を i とすると、a[i] は x 以上で最小の要素、a[i-1] は x 未満で最大の要素です。最近傍はこのどちらかなので、両方見ないと取り逃します。

1
from bisect import bisect_left
2

3
def nearest(a, x):
4
    """a はソート済み。x に最も近い要素を返す。"""
5
    i = bisect_left(a, x)
6
    cands = []
7
    if i < len(a):
8
        cands.append(a[i])
9
    if i > 0:
10
        cands.append(a[i - 1])
11
    return min(cands, key=lambda v: abs(v - x))

端のガードが要ります。x が全要素より大きいと i == len(a) になって a[i] が IndexError、全要素より小さいと i == 0 で a[i-1] が末尾を指してしまいます。後者はエラーにならず誤った値を返すので、こちらの方が厄介です。

元ネタは AtCoder ABC212 C（Min Difference）で、片方をソートしてもう片方の各要素で最近傍を引く形です。