演習課題「k番目の値」
整数n,m,kと長さnの配列a,長さmの配列bが与えられるので、各i,jに対してa[i]-b[j]で表される合計n×m個の整数のうち、小さい方からk番目の値を求めてください。
すでに入力を行うコードと関数lower_bound,upper_boundが実装されているので、コードを書き足して完成させてください。
期待する出力値
-3
＃07:数列のk番目
このチャプターでは、レベルアップ問題集「二分探索メニュー」の「長い長い数列」の問題を解いていきます。
def lower_bound(a, n, x):
left, right = 0, n
while left != right:
mid = (left + right) // 2
if a[mid] >= x:
right = mid
else:
left = mid + 1
return left
def upper_bound(a, n, y):
left, right = 0, n
while left != right:
mid = (left + right) // 2
if a[mid] > y:
right = mid
else:
left = mid + 1
return left
n = int(input())
a = [int(x) for x in input().split()]
m = int(input())
b = [int(x) for x in input().split()]
k = int(input())
# 配列(リスト)bを昇順にソート
b.sort()
# 変数left,rightをそれぞれ-1と2000000000で初期化
left, right = -1, 2000000000
# leftとrightの差が1でない間
while right-left != 1:
# 変数midに(left+right)/2を代入
mid = (left + right) // 2
# 個数を表す変数countを0で初期化
count = 0
# iを0からn-1まで繰り返す
for i in range(n):
# upper_bound(b,m,a[i]+mid)-lower_bound(b,m,a[i]-mid)をcountに加算
count += upper_bound(b, m, a[i]+mid) - lower_bound(b, m, a[i]-mid)
# もしcountがk以上なら
if count >= k:
# rightをmidで更新
right = mid
# そうでなければ
else:
# leftをmidで更新
left = mid
# rightを出力
print(right)
6
1 2 3 4 5 6
6
1 2 3 4 5 6
6
6
1 2 3 4 5 6
6
1 2 3 4 5 6
7