100日後にエンジニアになるキミ - 61日目 - プログラミング - 探索について

昨日までのはこちら

[100日後にエンジニアになるキミ - 59日目 - プログラミング - アルゴリズムについて](https://qiita.com/otupy/items/f1a5e81633b868f3b5ed)

[100日後にエンジニアになるキミ - 53日目 - Git - Gitについて](https://qiita.com/otupy/items/0abaad82a7f3fea73f1f)

[100日後にエンジニアになるキミ - 42日目 - クラウド - クラウドサービスについて](https://qiita.com/otupy/items/d1765f1541a104ed6133)

[100日後にエンジニアになるキミ - 36日目 - データベース - データベースについて](https://qiita.com/otupy/items/7af17635d576677606dc)

[100日後にエンジニアになるキミ - 24日目 - Python - Python言語の基礎1](https://qiita.com/otupy/items/6d1e5453f530e07b7aec)

[100日後にエンジニアになるキミ - 18日目 - Javascript - JavaScriptの基礎1](https://qiita.com/otupy/items/2f71d5f9c754b29d9555)

[100日後にエンジニアになるキミ - 14日目 - CSS - CSSの基礎1](https://qiita.com/otupy/items/61a97863f6df14171994)

[100日後にエンジニアになるキミ - 6日目 - HTML - HTMLの基礎1](https://qiita.com/otupy/items/cd2315dcb38671cfded0)

## 探索について

プログラミングにおける`探索`とは求めるデータを探し出す事です。

データの形もデータの探し方にも色々あります。

### 線形探索(linear search)

データを`リスト`に格納している時はリストの先頭から順番に
リストの最後まで見ていけば欲しいデータが見つかる事でしょう。

このような探索方法を`線形探索(linear search)`と言っています。
順番に調べるだけなのでシンプルで実装しやすいです。

次の例は簡単な線形探索の例です。

```python
data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
target = 4559
flg = False

## 線形探索の例
def linear_search(data, val):
    for x in data:
        if x == val:
            return True
    return False

print(linear_search(data, target))
```
True

比較的わかりやすいアルゴリズムだと思いますが
値が見つかるまで全て調べる必要があるのデータが増えると大変です。

リストの先頭からの順番に数値を探していますが、リストの後方に有ると
かなり時間がかかります。

平均だと$\frac{n + 1}{2}$の比較回数
最悪$O(n)$の処理になってしまいます。

### 二分探索(binary search)

リストでもデータ数が増えても高速に探し出す方法を考えると
`線形探索`では難しくなります。

辞書や電話帳のように、ある値を見た際に、目的の値がそれよりも
大きいのか小さいのかで判断する方法として
探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法を
`二分探索`と言っています。

```python
# 二分探索の例
def binary_search(data, num):
    left , right = 0 , len(data) - 1
    while left <= right:
        m = (left + right) // 2
        if data[m] == num:
            return m
        elif data[m] < num:
            left = m + 1
        else:
            right = m - 1
    return -1

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
data.sort()
print(data)
print(binary_search(data, 5119))
```

`二分探索`を可能にするにはデータがソートされている必要があります。
探索の前にデータを並び替えておきます。


### 木構造データの探索(breadth search)

リストに格納されているデータを探索する場面で無く
階層構造になっているデータの中から目的のデータを探し出すとします。

例えばWEBサイトのような木のような構造のデータのなかから
目的のページを探し出すような場合
その際に考えられるのが`幅優先探索`と`深さ優先探索`です。

### 幅優先探索(breadth first search)

探索を開始する場所から近いものをリスト化し、それぞれを細かく調べて行く方法を
`幅優先探索(BFS)`と言います。

```python
# BFS(幅優先探索)
import os
from collections import deque
 
def bfs(path):
    q = deque([])
    q.append(path)
    while len(q) > 0:
        p = q.popleft()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path)
    return q

print(bfs('./'))
```

### 深さ優先探索(depth first search)

`幅優先探索`に対して目的のほうへ進めるだけ進み、進めなくなったら戻る方法を
`深さ優先探索(DFS)`と言っています。

`バックトラック法`とも呼ばれています。

```python
import os
from collections import deque
 
def dfs(path):
    q = deque([]) 
    q.append(path)
    while len(q) > 0:
        p = q.pop()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path) 
    return q

print(dfs('./'))
```



## まとめ

データの探索方法も多岐にわたり
データの組み方、探し方一つで計算量、実行速度が大きく変わります。

扱うデータに合わせて最適なデータ形式と
探索アルゴリすむを考えてみましょう。

君がエンジニアになるまであと39日

## 作者の情報
乙pyのHP：
http://www.otupy.net/

Youtube：
https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter：
https://twitter.com/otupython