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