演習課題「二分探索で位置を求める」
整数n,xと長さnの昇順にソートされた配列aが与えられるので、この配列に含まれるxの添字を出力してください。ただし、xが含まれていない場合は-1を出力してください。
入出力用のコードがすでに用意されているので、関数binary_searchにコードを書き足してプログラムを完成させてください。
期待する出力値
2
＃01:二分探索
このチャプターでは、さまざまな処理を高速化するアルゴリズムである二分探索について学習します。
def binary_search(n, x, a):
# 変数left,rightをそれぞれ0とn-1で初期化
left, right = 0, n-1
# rightがleft以上である間
while right >= left:
# 変数midに(left+right)/2を代入
mid = (left + right) // 2
# もしa[mid]がxに等しいなら
if a[mid] == x:
# trueを返す
return True
# もしa[mid]がxより大きいなら
elif a[mid] > x:
# rightにmid-1を代入
right = mid - 1
# そうでなければ
else:
# leftにmid+1を代入
left = mid + 1
# falseを返す
return False
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
print("Yes" if binary_search(n, x, a) else "No")
3 1
1 3 8
3 2
1 3 8