AOJ ALDS1_4 B BinarySearch - 電波ビーチ

みんなだいすきバイナリサーチです。何度メモっても忘れる。

概要

ソート済み配列があったときそこにxが含まれているかどうか以外に、「xを最初に越える最小のy」とか「xを下回る最大のy」みたいなのを抽出するタイプにがんがん使います、たぶん。

手順

ソート済みの配列arrayを用意し、その中で探し出したい値をtargetとして定義
left=0, right=array.lengthとする。これらが配列のインデックスを表す。array[(left+right)/2]==targetならば探索終了
array[(left+right)/2)]<targetならばtargetはarrayの中央部分より後にあるのでそこだけを調べれば良い。探索範囲を狭めるためleft=(left+right)/2+1とし探索再開。
array[(left+right)/2]>targetならば逆に中央よりも前にあるのでright=(left+right)/2とする。
3, 4を2になるまで繰り返す。

です。

実装してみた

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

def lower_bound(lis, target):
    left, right = 0, n
    while left<right:
        mid = (left+right)//2
        if lis[mid]==target:
            return True
        elif target<lis[mid]:
            right = mid
        else:
            left = mid+1
    return False

cnt = 0
for i in range(q):
    cnt = cnt+1 if lower_bound(s, t[i]) else cnt
print(cnt)

解説の擬似コードどおりにやっただけです。問題は「含まれるかどうか」なのでboolで返しちゃってます。ちなみに、要はどちらの配列にも含まれるやつの数が答えなので、バイナリサーチを使わなくても

input()
s = set(input().split())
input()
t = set(input().split())
print(len(s&t))

とかいう荒業でいけるみたいです。アルゴリズム完全無視。

※補足 bisectモジュール

標準モジュールであるところのbisectは二分探索用のモジュールで、見てみると中身は4つの関数で構成されていました。

insort_right(a, x, lo=0, hi=None)
- ソート済みリストaにxをしかるべき場所に挿入する。既にxと同値の要素があった場合はその一番右に挿入する。lo, hiで探索する範囲の指定ができる
insort_left(a, x, lo=0, hi=None)
- insort_rightの左バージョン
bisect_right(a, x, lo=0, hi=None)
- aのしかるべき場所にxを挿入する際のインデックスを返す。既にxがあった場合はその一番右となるインデックスを返す。
bisect_left(a, x, lo=0, hi=None)
- bisect_leftの左バージョン

つまり配列のどこに追加できるかを返すやつなので、今回のような問題では使い勝手が悪そうです。が、覚えておくとどっかで使うかもしれない（バイナリサーチくらいフルスクラッチで書けるようになっておくのが一番いいのでは。。）