こんにちは。
いつも応援有難うございます m(_ _)m
9/23 から投稿を開始して、そろそろ 3 週間が経とうとしています。
楽しいことは あっ という間ですね(笑)。
さて、今回は探索です。
最初は線形探索から行きましょう。
構えなくて大丈夫です。
こんな感じで左から順番に、探したい値と赤字が一致しているか確認するだけです。
※すいません、途中で図が切れてて。。
早速、書いてみましょう。
def search(x,key):
for i in range(len(x)):
if x[i] == key:
print(f"value is placed at x[{i}]")
break
#最終項 x[6] != key の場合、前述の if x[i] == key を pass するので、
#そのまま以下の if 文に入ります。
#i == len(x)-1 なら、fail です。
if i == len(x)-1:
print("fail to serch")
break
if __name__ == "__main__":
x = [6,4,3,2,1,2,8] # 配列を指定
key = int(input("enter search value: ")) # 探したい値を入力
search(x,key)
では次は、2分探索です。
線形探索との前提条件が大きく異なります。その違いをイメージにしました。
線形探索の場合は、与えられたものを端から比較していくのですが、
2分探索は、そうは行きません。一旦、整列します。出だしが全然違うので注意が必要です。
(? _ ?)(? _ ?)(?_?)
はい、構わず次のステップに行きます。
仮に 3 を探している場合、中央値との比較で一発で発見できます(笑)
では、3 より小さい値を探している場合はどうでしょうか。
探したい値が1の場合どうしましょうか。
[1 , 2 , 2] の中央値 2 でもない場合は、更にそれ以下の
1 が格納されている x[0] を見るだけです。
もし、それでも探している値が無ければ、探し物はそもそも、
用意された配列には存在しない事になります。
一旦、整理しないとイケないメンドイ アルゴですが、なかなか有名らしいです。
今回は再帰で書いてみました。
def binary_search(x,left,right,key):
cen = (left + right)//2
if left > right:
print(f"left is {left},right is {right}")
print("faile to search")
return None
if x[cen] == key:
return print(f"found at x[{cen}]")
#中央値 x[cen] が探し物 key より大きい場合
if x[cen] > key:
print(f"left is {left},cen is {cen}")
binary_search(x,left,cen-1,key)#cen-1 の "-1" がミソです!!!
#中央値 x[cen] が探し物 key より小さい場合
if x[cen] < key:
print(f"cen is {cen},right is {right}")
binary_search(x,cen+1,right,key)#cen+1 の "+1" がミソです!!!
if __name__ == "__main__":
x =[1,2,2,3,4,6,8]
binary_search(x,0,len(x)-1,1)
left is 0,cen is 3
left is 0,cen is 1
found at x[0]
左側を選択し、徐々に狭めていますね。
配列長を大きくしてイメージを作り直してみました。
このほうが分かりやすいかもしれません(中央値は赤、探し物が 7 の場合)。
もし、探し物が7じゃなかったらどうしますか？
以下の記述のミソに着目してみてください。
#中央値 x[cen] が探し物 key より大きい場合
if x[cen] > key:
print(f"left is {left},cen is {cen}")
binary_search(x,left,cen-1,key)#cen-1 の "-1" がミソです!!!
#中央値 x[cen] が探し物 key より小さい場合
if x[cen] < key:
print(f"cen is {cen},right is {right}")
binary_search(x,cen+1,right,key)#cen+1 の "+1" がミソです!!!
念のため実行してみると以下のコメントが見えてきます。
left is 5,right is 4
faile to search
そうなんです。left > right が実現しています。
どういう事でしょうか？
探し物が 6 だった場合、
記述にある if x[cen] > key:に突入します。
その結果、binary_search(x,left,cen-1,key) となります。
この時点で、left == right なので、前述の式を考えると
left > right になりますよね!??。
これが逆転の仕組みです。
ここまで来たら、何もないって言えますよね？？
※逆のパターン(if x[cen] < key:)もしかりです(≧▽≦)
もっとシンプルに書ける方が居たら、
申し訳ありませんが御教示宜しくお願い致します。m(_ _)m