数値を線形探索/2分探索で探してみよう

こんにちは。
いつも応援有難うございます m(_ _)m
9/23 から投稿を開始して、そろそろ 3 週間が経とうとしています。
楽しいことは あっ という間ですね(笑)。

さて、今回は探索です。
最初は線形探索から行きましょう。
構えなくて大丈夫です。
![図1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/cb11c8a4-a411-2335-dd37-bd75cccedb05.png)
こんな感じで左から順番に、探したい値と赤字が一致しているか確認するだけです。
※すいません、途中で図が切れてて。。
早速、書いてみましょう。

```linear_search.py
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.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/59565094-bd40-b92a-16ef-94e2df5f550c.png)
線形探索の場合は、与えられたものを端から比較していくのですが、
2分探索は、そうは行きません。一旦、整列します。出だしが全然違うので注意が必要です。
(? _ ?)(? _ ?)(?_?)
はい、構わず次のステップに行きます。
![図3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/ba4bd981-cfde-988a-6a21-a149be802c8c.png)
仮に **3** を探している場合、中央値との比較で一発で発見できます(笑)
では、3 より小さい値を探している場合はどうでしょうか。
![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/7e44cda0-5226-89df-506c-d0723522824c.png)
探したい値が**1**の場合どうしましょうか。
[1 , 2 , 2] の中央値 2 でもない場合は、更にそれ以下の
1 が格納されている x[0] を見るだけです。
もし、それでも探している値が無ければ、探し物はそもそも、
用意された配列には存在しない事になります。
一旦、整理しないとイケないメンドイ アルゴですが、なかなか有名らしいです。
今回は再帰で書いてみました。

```binary_search.py
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)
```

```実行結果.py
left is 0,cen is 3
left is 0,cen is 1
found at x[0]
```

左側を選択し、徐々に狭めていますね。
配列長を大きくしてイメージを作り直してみました。
このほうが分かりやすいかもしれません(中央値は赤、**探し物が 7 の場合**)。
![図5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/afbd8e8e-a00e-cd80-e7e5-c54a6bcc108a.png)
もし、探し物が**7**じゃなかったらどうしますか？
以下の記述の**ミソ**に着目してみてください。

```miso.py
    #中央値 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" がミソです!!!
```

念のため実行してみると以下のコメントが見えてきます。

```実行結果.py
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