二分探索メニュー 問題セット | paizaラーニング Python解答例

paizaでPythonを学ぼう
スポンサーリンク

はじめに

この記事ではpaizaラーニングのレベルアップ問題集にある二分探索メニューのPython解答例を掲載する。解答例へのリンク一覧はpaizaでPythonを学ぼうに掲載。

記事執筆時点でC++の解答コードは載っているのだが、Pythonの解答はない。参考までに私の解答を載せておく。「長い長い数列」の解答は後日追加する予定。二分探索は英語でbinary search(バイナリーサーチ)と呼ばれる。

ある範囲に含まれている整数の個数

値の探索(Cランク)

二分探索アルゴリズムの基本を学ぶ問題。問題文に載っているこのサンプルコードをPythonに落とし込めば良い。

/**
ソート済みの数列 A に 値 k が含まれているなら true を、含まれていないなら no を返す
*/
binary_search(A : 数列, n : 数列のサイズ, k : 探索する値)
    // 探索範囲 [left, right]
    left = 0
    right = n-1
    
    // 探索範囲を狭めていく
    while left <= right

        // 探索範囲の中央
        mid = (left + right) / 2

        if A[mid] == k then
            return true
        else if A[mid] < k then
            left = mid+1
        else 
            right = mid-1
    
    return false

defを使わない場合。

n = int(input())
array = [int(_) for _ in input().split()]
q = int(input())

for i in range(q):
    k = int(input())

    left = 0
    right = n - 1
    ans = None

    while left <= right:
        mid = (left + right) // 2
        if array[mid] == k:
            ans = 'Yes'
            break
        elif array[mid] < k:
            left = mid + 1
        else:
            right = mid - 1

    if not ans:
        ans = 'No'
    print(ans)

def文を使った例。

def binary_search(array, k):
    left = 0
    right = n - 1
    print('k = ' + str(k))

    while left <= right:
        mid = (left + right) // 2
        print(array[mid])

        if array[mid] == k:
            return 'Yes'
        elif array[mid] < k:
            left = mid + 1
        else:
            right = mid - 1

    return 'No'


n = int(input())
array = [int(_) for _ in input().split()]
q = int(input())

for i in range(q):
    k = int(input())
    print(binary_search(array, k))

lower_bound(Bランク)

問題ページに載っている擬似コードをPythonに落とし込めば良い。

/**
    A_i >= k を満たす最小の i を返す
    A_i >= k を満たす i が存在しない場合は n を返す
*/
binary_search(A : 数列, n : 数列のサイズ, k : 基準)
    // 探索範囲 [left, right]
    left = 0
    right = n
    
    // 探索範囲を狭めていく
    while left < right
        // 探索範囲の中央
        mid = (left + right) / 2

        if a[mid] < k then
            // a[0] ~ a[mid] は k 未満なので調べる必要が無い
            left = mid+1
        else
            right = mid
    
    return right
n = int(input())
array = [int(_) for _ in input().split()]
array = sorted(array)
q = int(input())

for i in range(q):
    k = int(input())

    left = 0
    right = n

    while left < right:
        mid = (left + right) // 2
        if array[mid] < k:
            left = mid + 1
        else:
            right = mid

    print(n - right)

upper_bound(Bランク)

こちらはlower_boundを少し修正するだけ。

n = int(input())
array = [int(_) for _ in input().split()]
array = sorted(array)
q = int(input())

for i in range(q):
    k = int(input())

    left = 0
    right = n

    while left < right:
        mid = (left + right) // 2
        if array[mid] > k:
            right = mid
        else:
            left = mid + 1

    print(n - right)

ある範囲に含まれている整数の個数(Bランク)

lower_boundとupper_boundを組み合わせれば解答出来る。いきなりこの問題に挑戦した時は分からなくて途方に暮れたが、上の問題を解いたら簡単に理解できた。やはり初心者は人の書いた動くコードを見て真似するほうが学習効率が遥かに高いと実感した。このコードをイチから自力で考えるのは時間がかかりすぎる。

n = int(input())
array = [int(_) for _ in input().split()]
array = sorted(array)
q = int(input())

for i in range(q):
    k1, k2 = map(int, input().split())

    left = 0
    right = n

    while left < right:
        mid = (left + right) // 2
        if array[mid] < k1:
            left = mid + 1
        else:
            right = mid

    ans1 = n - right

    left = 0
    right = n

    while left < right:
        mid = (left + right) // 2
        if array[mid] > k2:
            right = mid
        else:
            left = mid + 1

    ans2 = n - right
    print(ans1 - ans2)

長い長い数列

準備中

コメント

当ブログのコンテンツが気に入ったら広告ブロックの解除(ホワイトリスト化)をご検討下さい。

Please disable your adblocker or whitelist this site!

タイトルとURLをコピーしました