58 探索アルゴリズム

58.1 線形探索

線形探索（linear search, sequential search）は，与えられたリストから目的の要素があるかどうかを順番に調べる最も単純なアルゴリズムの一つである．

例えば，[3, 5, 2, 4, 1]というリストがあるとする．このリストから4を探す場合，次のように進める．

3を読み取る．4ではないので次へ．
5を読み取る．4ではないので次へ．
2を読み取る．4ではないので次へ．
4を読み取る．これが目的の要素である．
探索を終了．

以上は線形探索の一例である．このアルゴリズムを数学記号を用いて，より一般的に表現すると，次のようになる．

$n$ 個の要素を持つリスト $l$ があるとき，ある目的要素 $x$ が存在するかどうかを調べる線形探索は，次に示す

\begin{algorithm} \caption{Linear search} \begin{algorithmic} \State $\texttt{found} \gets \texttt{False}$ \State $i \gets 1$ \While{$i \leq n$ and $\texttt{found} = \text{False}$} \If{$l_i = x$} \State $\texttt{found} \gets \texttt{True}$ \Else \State $i \gets i + 1$ \EndIf \EndWhile \State \textbf{return} $\texttt{found}$ \end{algorithmic} \end{algorithm}

以下は，PythonとC言語での実装例である．

def linear_search(l, x):
    found = False
    i = 0
    while i < len(l) and not found:
        if l[i] == x:
            found = True
        else:
            i += 1
    return found

if __name__ == "__main__":
    l = [3, 5, 2, 4, 1]
    x = 4
    print(linear_search(l, x))  # True

#include <stdio.h>

int linear_search(int l[], int n, int x) {
    int found = 0; // 0: False, 1: True
    int i = 0;
    while (i < n && !found) {
        if (l[i] == x) {
            found = 1;
        } else {
            i++;
        }
    }
    return found;
}
int main() {
    int l[] = {3, 5, 2, 4, 1};
    int n = sizeof(l) / sizeof(l[0]);
    int x = 4;
    printf("%d\n", linear_search(l, n, x));  // 1 (True)
    return 0;
}

58.1.1 整列配列に対する線形探索

ソートされた配列を整列配列（sorted array）と呼ぶ．例えば，[1, 2, 3, 4, 5]，['a', 'c', 'd', 'e']，["Alice", "Bob", "Charlie"]などが整列配列である．

このような整列配列に対して，ある要素が存在するかどうかを調べる場合，線形探索を用いることもできるが，効率的ではない．最悪のケースにおいて，全ての要素を調べる必要となる．

線形探索よりも効率的な方法があるかを考えよう．

58.2 二分探索

二分探索（binary search）は，整列配列に対して効率的に要素を探すアルゴリズムである．整列配列の中央の要素と目的の要素を比較し，等しくなければ，半分の要素を排除し，残りの半分に対して再度同じ操作を繰り返す．これを目的の要素が見つかるまで続ける．

例えば，[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]という整列配列から10を探す場合，次のように進める．

中央の要素は5．10は5より大きいので，[6, 7, 8, 9, 10]に絞る．
中央の要素は8．10は8より大きいので，[9, 10]に絞る．
中央の要素は9．10は9より大きいので，[10]に絞る．
中央の要素は10．これが目的の要素である．
探索を終了．

線形探索は10回の要素を調べる必要があるが，二分探索は4回の要素を調べるだけで済む．

要素数が奇数の場合，中央の要素は真ん中の要素を指す．偶数の場合は，中央の2つの要素のうち，どちらを選んでもよい．ここでは左側の要素を選ぶことにする．

$n$個の要素を持つ整列配列$l$があるとき，ある目的要素$x$が存在するかどうかを調べる二分探索は，次のように定義される．

\begin{algorithm} \caption{Binary search} \begin{algorithmic} \State $\texttt{found} \gets \texttt{False}$ \State $L \gets 1$ \State $R \gets n$ \While{$L \leq R$ and $\texttt{found} = \text{False}$} \State $m \gets \lfloor (L + R) / 2 \rfloor$ \If{$l_m = x$} \State $\texttt{found} \gets \texttt{True}$ \ElsIf{$l_m < x$} \State $L \gets m + 1$ \Else \State $R \gets m - 1$ \EndIf \EndWhile \State \textbf{return} $\texttt{found}$ \end{algorithmic} \end{algorithm}

$L$ と $R$ はそれぞれ，探索範囲の左端と右端を指すとし，$\lfloor (L + R) / 2 \rfloor$ で中央の要素を求める．ここでは，$\lfloor x \rfloor$ は $x$ の小数点以下を切り捨てた整数を表し，$x$ のfloorと呼ばれる．

例えば，$L = 1$，$R = 10$ の場合，中央の要素は \[ \lfloor (1 + 10) / 2 \rfloor = \lfloor 5.5 \rfloor = 5 \] となる．また，$L = 6$，$R = 10$ の場合，中央の要素は $\lfloor (6 + 10) / 2 \rfloor = 8$ となる．

以下は，PythonとC言語での実装例である．

def binary_search(l, x):
    found = False
    L = 0
    R = len(l) - 1
    while L <= R and not found:
        m = (L + R) // 2
        if l[m] == x:
            found = True
        elif l[m] < x:
            L = m + 1
        else:
            R = m - 1
    return found

if __name__ == "__main__":
    l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    x = 9
    print(binary_search(l, x))  # True

#include <stdio.h>

int binary_search(int l[], int n, int x) {
    int found = 0; // 0: False, 1: True
    int L = 0;
    int R = n - 1;
    while (L <= R && !found) {
        int m = (L + R) / 2;
        if (l[m] == x) {
            found = 1;
        } else if (l[m] < x) {
            L = m + 1;
        } else {
            R = m - 1;
        }
    }
    return found;
}
int main() {
    int l[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(l) / sizeof(l[0]);
    int x = 9;
    printf("%d\n", binary_search(l, n, x));  // 1 (True)
    return 0;
}