演習課題「upper_bound」
整数n,qと長さnの配列a,長さqの配列kが与えられるので、各k[i]について、この配列のk[i]以下である要素の個数を出力してください。
入出力用のコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。
期待する出力値
1
3
5
＃02:x以上の個数
このチャプターでは、レベルアップ問題集「二分探索メニュー」の「lower_bound」の問題を解いていきます。
# 関数lower_bound(a,n,x)を定義
def lower_bound(a, n, x):
# 変数left,rightをそれぞれ0とnで初期化
left, right = 0, n
# leftとrightが一致しない間
while left != right:
# 変数midに(left+right)/2を代入
mid = (left + right) // 2
# もしa[mid]がx以上なら
if a[mid] >= x:
# rightをmidで更新
right = mid
# そうでなければ
else:
# leftをmid+1で更新
left = mid + 1
# leftを返す
return left
n = int(input())
a = [int(x) for x in input().split()]
q = int(int(input()))
# 配列(リスト)aを昇順にソート
a.sort()
k = [0] * q
for i in range(q):
k[i] = int(input())
# n-lower_bound(a,n,k[i])を出力
print(n - lower_bound(a, n, k[i]))
3
8 1 3
1
3
10
10 9 8 7 6 5 4 3 2 1
2
5
7