競技プログラミング めぐる式二分探索

Question

前提

使用言語 python

質問内容

pythonで競技プログラミングの勉強をしています.
AOJの二分探索の問題https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_Bを以下のソースコードを使用して解いたのですが

def i_input(): return int(input())
def i_map(): return map(int, input().split())


# listにitemがあったらTrue, なければFalseを返す
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return True
        elif guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return False


n = i_input()
s = list(i_map())
q = i_input()
t = list(i_map())

count = 0
for i in t:  # tの要素がsに含まれているか確認
    if binary_search(s, i):
        count += 1
print(count)

めぐる式二分探索を使って解けずに困っています.(どのように判定式を記述すれば良いか分からない)

def is_ok(mid):
    """
    二分探索中の判定
    :param mid:
    """
    # ここの条件式をどう書けばよいかわかりません
    pass


def meguru_bisect(ng, ok):

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

全体のソースコード(修正・追加箇所)

# スニペット（再利用可能なソースコード）
def i_input(): return int(input())


def i_map(): return map(int, input().split())


def is_ok(key):
    # ここの部分の判定方法がわかりません.

    if s[key] == i:
        return True
    else:
        return False



def binary_search(ng, ok):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ng

n = i_input()
s = list(i_map())
q = i_input()
t = i_map()

count = 0
for i in t:
    #　ngがリストの右端までいくとtの要素(i)を含んでいないと判定
    if binary_search(-1, n) != n:
        count += 1

print(count)

実現したいこと

• めぐる式二分探索を使用してhttps://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_Bを解く.

最後に

初めての質問 & Markdown記法なので至らない点があると思いますがよろしくお願いします.

Answer 1

def i_input(): return int(input())
def i_map(): return map(int, input().split())

def is_ok(index, key):
    return s[index] >= key


def meguru_bisect(key,m):
    ng = -1
    ok = m
    while (abs(ok - ng) > 1) :
        mid = (ok + ng) // 2
        if is_ok(mid, key):
            ok = mid
        else:
            ng = mid

    return ok

n = i_input()
s = list(i_map())
q = i_input()
t = list(i_map())

count = 0

for i in t:
    #一致する数があるか
    res = meguru_bisect(i, n)
    if res != n and s[res] == i:
        count += 1
print(count)

Comments

[退会済みユーザー]

t[]にs[]の最大値よりも大きな値が含まれる場合、meguru_bisectはnを返すので s[meguru_bisect(i, n)] はIndexErrorになりますよ。

[teaspoooon]

cm67809733さん
回答ありがとうございます。
ご指摘の通り、二分探索についてまだ完全に理解できず、探り探り取り組んでいる状況です。
cm67809733さんの回答を参考にもう一度取り組んでみます。

Answer 2

meguru_bisectを「リストsのx番目の要素が今回調べたい値以上となるような最小のインデックス値xを探す関数」として実装してみてはどうでしょう。
(pythonのbisectライブラリに含まれるbisect_leftと同じことをするイメージ)

def i_input(): return int(input())
def i_map(): return map(int, input().split())

def is_ok(mid):
    return s[mid] >= i          # i は for i in t: での i

def meguru_bisect(ng, ok):
    # リストsの中で s[x] >= i となるような最小のインデックス値xを探す
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = i_input()
s = list(i_map())
q = i_input()
t = list(i_map())

count = 0
for i in t:
    res = meguru_bisect(-1, n)
    if res != n and s[res] == i:
        count += 1
print(count)

Comments

[teaspoooon]

dljfab さん
回答ありがとうございます。
詳しい解説&コメントとても分かりやすかったです。
特に「bisect_leftと同じことをするイメージ」は理解の助けになりました。
回答を元にもう一度、二分探索について勉強します。