問題: 二分探索 (Python)

二分探索 (Python)

問題

1行目に空白区切りの整数の列、2行目に探す整数を入力として受け取ります。整数の列を昇順にソートしてから二分探索を行い、見つかった位置（0から始まるインデックス）と比較回数を表示してください。

入力例

42 7 19 88 3 56 25 71 64 10
64

出力例

ソート結果: [3, 7, 10, 19, 25, 42, 56, 64, 71, 88]
64はインデックス7にあります（比較2回）

残り時間: 00:00

速度: 0 文字/分

参照コード

コピーはできません。自分でタイピングしてください。

def binary_search(data, target):
    """ソート済みのリストから target の位置と比較回数を返す"""
    low, high = 0, len(data) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if data[mid] == target:
            return mid, steps
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

def main():
    data = sorted(map(int, input().split()))
    target = int(input())
    index, steps = binary_search(data, target)
    print(f"ソート結果: {data}")
    if index >= 0:
        print(f"{target}はインデックス{index}にあります（比較{steps}回）")
    else:
        print(f"{target}は見つかりません（比較{steps}回）")

if __name__ == "__main__":
    main()

二分探索 (Python)

問題

入力例

出力例

参照コード

入力エリア