トップページ -> AOJの解答例 -> ITP2_6の解答例

ITP2_6の解答例(Python)

二分探索に関する問題です．

1. ITP2_6_A: Binary Search

二分探索を行う問題です．長さnのsortされているリストlに対して以下の処理を行うことでleftとrightで探している要素を挟み撃ちにします．

処理1．left=0, right=n-1 とします．
処理2．leftとrightの中点half(=(left+right)/2) について探している要素がl[half]より右にあるか左にあるかを調べます．
処理3．探している要素が右にある場合はleft=half+1，左にある場合はright=half-1と更新し区間を絞り込み処理2に戻ります．

この処理によって区間が何度も半分に割られて最後まで見つからなければ1点に潰れます．例えばl=[0,1,2,3,4,5,6,7,8,9,10] から 7 を探したい場合は，
(1) left=0, right=11, half=int(11/2)=5 l[half]=5なので7はhalfより右側にあります．よってleft=6に更新されます．
(2) left=6, right=11, half=int(17/2)=8 l[half]=8なので7はhalfより左側にあります．よってright=7に更新されます．
(3) left=6, right=7, half=int(13/2)=6 l[half]=6なので7はhalfより右側にあります．よってleft=7に更新されます．
(4) left=7, right=7, half=7 l[half]=7 探している要素が見つかりました．


# ITP2_6_A

# 二分探索の関数
def binary_search(n,N):
    left = 0
    right = len(N)-1
    while left <= right:
        half = int((right + left)/2)
        if N[half] == n:
            return 1
        # n が half より左側にある
        elif N[half] > n:
            right = half-1
        # n が half より右側にある
        elif N[half] < n:
            left = half+1
            
    return 0

dummy = int(input())
N = list(map(int,input().split(" ")))
m = int(input())

for _ in range(m):
    n = int(input())
    print(binary_search(n,N))

ITP2_6_Cでbisect_leftと同じ処理を書きますが，bisect_leftを使うことでも解くことができます． bisect_leftを使う場合は二分探索の処理を自分で書く必要はないです．


# ITP2_6_A
# bisect_left を使うやり方
from bisect import bisect_left

length = int(input())
N = list(map(int,input().split(" ")))
m = int(input())

for _ in range(m):
    n = int(input())
    b_left = bisect_left(N,n) # b_left: 順序を保ったままNにnを挿入できる位置
    if b_left <= length-1:
        print(int(n == N[b_left]))
    else:
        print(0)

2. ITP2_6_B: Includes

与えられた集合Aと集合Bの包含関係を調べる問題です．


# ITP2_6_B

n = int(input())
N = set(map(int,input().split(" ")))
m = int(input())
M = set(map(int,input().split(" ")))
# M <= N で包含関係を調べることができる
print(int(M <= N))

3. ITP2_6_C: Lower Bound

昇順に並んだ数字のリストに対して，その数字が初めて現れる場所を求める問題です．先ほど定義した二分探索の関数を改良して求めました．


# ITP2_6_C
# lower boundを# ITP2_6_Aの二分探索を改良して求める

# 二分探索の関数
def binary_search(n,N):
    left = 0
    right = len(N)-1
    lower_bound = len(N) # 存在しない場合はNの長さ
    while left <= right:
        half = int((right + left)/2)
        # n が half より左側にある (一致しても同じ数字が左側にあるかもしれないことに注意)
        if N[half] >= n:
            right = half-1
            lower_bound = half # lower_boundを更新
        # n が half より右側にある
        elif N[half] < n:
            left = half+1
            
    return lower_bound

n = int(input())
N = list(map(int,input().split(" ")))
m = int(input())

for _ in range(m):
    k = int(input())
    print(binary_search(k,N))

また，bisect_leftを使うことでも上と同じ処理ができます．
【外部サイト】bisect --- 配列二分法アルゴリズム


# ITP2_6_C
# bisect_left を使うやり方
from bisect import bisect_left

n = int(input())
N = list(map(int,input().split(" ")))
m = int(input())

for _ in range(m):
    k = int(input())
    print(bisect_left(N,k))

4. ITP2_6_D: Equal Range

lower bound, upper boundを求める問題です． lower bound, upper boundと大層な名前が付いているので身構えますが，先ほどのbinary_searchを使うと入力kに対して求めたいものは，binary_search(k,N)とbinary_search(k+1,N)です．もちろんこの問題もbisect_leftが使えます．


# ITP2_6_D

# 二分探索の関数 lower_bound
def binary_search(n,N):
    left = 0
    right = len(N)-1
    lower_bound = len(N) # 存在しない場合はNの長さ
    while left <= right:
        half = int((right + left)/2)
        # n が half より左側にある (一致しても同じ数字が左側にあるかもしれないことに注意)
        if N[half] >= n:
            right = half-1
            lower_bound = half # lower_boundを更新
        # n が half より右側にある
        elif N[half] < n:
            left = half+1
            
    return lower_bound

n = int(input())
N = list(map(int,input().split(" ")))
m = int(input())

for _ in range(m):
    k = int(input())
    # upper_bound が lower_boundより右なことを利用しなくても時間制限をクリアできました
    print(binary_search(k,N),binary_search(k+1,N))

<- 前へ戻る【目次に戻る】次へ進む ->