目指せAtcorder茶色
A11
B11
クリア!!
2分探索
要素が昇順の配列から特定の値を検索する場合、配列のちょうど真ん中の値と比較し、検索する値が、その真ん中の値より大きいければ、
配列の真ん中より下は検索する必要がないので、検索する範囲を半分に絞ることができる。
その操作を繰り返して、値を発見する方法。
pythonで実施する場合、配列の要素のindexの範囲を半分ずつにしていく。
左から昇順の配列A、検索する値をxとすると、検索範囲の一番左側のindexをhidari、一番右側をmigiとしたとき、配列の真ん中のindexは、（hidari＋migi）÷2になる。
これをaとすると、配列の要素の値は、A[a]となる。
A[a]とxを比較し、xの方が大きいければ、検索する値は、aより右側にあるとわかる。
そのため、検索範囲のhidariの値をa+1にすることにより、検索する範囲がa+1からmigiになり、範囲が半分になる。
xの方が小さければ、検索する値は、aより左側にあるとわかる。
そのため、検索範囲のmigiの値をa-1にすることにより、検索範囲がhidariからa-1になり、範囲が半分にある。
これを繰り返して、A[a]=xとなる値を探していく。
2分探索するコード(検索値があれば、配列のindexを、なければ-1を返す）
xが検索する値、Aが検索する配列とする。
def search(x,A):
hidari=0
migi=N-1
while hidari<=migi:
a=int((hidari+migi)/2)
if x>=A[a]:
hidari=a+1
if x==A[a]:
return a
if x<=A[a]:
migi=a-1
return -1
N=15 #配列Aの要素数
A=[9,18,25,27,28,29,36,39,42,45,46,55,59,64,72]
x=39
ans=search(x,A)
print(ans)