Skip to article frontmatterSkip to article content

探索アルゴリズム

法政大学

線形探索

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

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

  1. 3を読み取る。4ではないので次へ。

  2. 5を読み取る。4ではないので次へ。

  3. 2を読み取る。4ではないので次へ。

  4. 4を読み取る。これが目的の要素である。

  5. 探索を終了。

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

nn個の要素を持つリストllがあるとき、ある目的要素xxが存在するかどうかを調べる線形探索は、次のように定義される。

以下は、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

Program 1:Linear search in Python

#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;
}

Program 2:Linear search in C

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

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

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

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

二分探索

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

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

  1. 中央の要素は5。10は5より大きいので、[6, 7, 8, 9, 10]に絞る。

  2. 中央の要素は8。10は8より大きいので、[9, 10]に絞る。

  3. 中央の要素は9。10は9より大きいので、[10]に絞る。

  4. 中央の要素は10。これが目的の要素である。

  5. 探索を終了。

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

nn個の要素を持つ整列配列llがあるとき、ある目的要素xxが存在するかどうかを調べる二分探索は、次のように定義される。

以下は、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

Program 3:Binary search in Python

#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;
}

Program 4:Binary search in C

アルゴリズム
アルゴリズム発見
アルゴリズム
ソートアルゴリズム