ABC212 C問題[二分探索]

C - Min Difference

Difficultty : 246

■要約

　久々に参加したABCで解くことが出来なかった悔しい問題．二重ループでは余裕でTLEなので愚直でないことは分かる．過去に解いた問題で，配列関係の最小の〇〇や，最大の〇〇系はほぼ二分探索というツイートを見て二分探索を使うことは分かったが実装や考え方がさっぱりだった．今回真剣にとき直して，なんとなく苦手意識を持っていた二分探索を理解できた．（気がする．．）

今回の問題の肝は，数直線で考えて，方一方の配列を固定して，もう一方の数列の値を1つずつ見ていき，①その数直線上でどこにその値があって，②その左右の値との絶対値の最小の値を更新していく．という2つが大切になる．この①の部分で二分探索が使われるのだ！

■二分探索

　二分探索とは，ソートされた配列にある値xを挿入する場所を計算量O(logN)で探索してくれるアルゴリズムである．今回のように，ある値が，ある配列の何番目に含まれるか探したい時にぴったりなのだ．

 pythonではbisectモジュールを用いれば簡単に実装できる．特に使うのが，bisect_left関数で．以下のように使う．

bisect_left(a, x)
----引数-----
a:ソート済みリスト
x:挿入したい値
---返り値-----
何番目の要素に挿入されるか

　これを使えば，処理①の何番目に値が含まれるかが分かるので，②を行えば良い．

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort()

ans = 10**10+1
import bisect
"""
bisect_left(a, x)
----引数-----
a:ソート済みリスト
x:挿入したい値
---返り値-----
何番目の要素に挿入されるか
"""
for a in A:
 i = bisect.bisect_left(B, a) #配列Bのどこの位置に挿入されるか
 
 if 0 <= i - 1 < M:
   b1 = B[i-1] #左側
   ans = min(ans, abs(a - b1))
 if 0 <= i < M:
   b2 = B[i] #右側
   ans = min(ans, abs(a - b2))
   
print(ans)