バイナリーサーチ

バイナリーサーチ(二分探索とも呼ばれる)はソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズムです。

ソート済みの配列を分割するということはバイナリーサーチツリーを生成することになります。

検索範囲の分割はデータの大小関係をもとに行われます。

アルゴリズム分析

1. 配列をソートする(ここでは昇順でソートされたとする)
2. 配列の中央にある要素を調べる
3. 探索
   • 中央の要素が目的の値ではなく、目的のデータが中央の値より大きい場合、中央より後半の部分を調べる
   • 中央の要素が目的の値ではなく、目的のデータが中央の値より小さい場合、中央より前半の部分を調べる
4. 2.に戻る

注意

バイナリーサーチは値の比較によって検索範囲を絞りこむので、探索対象の配列がソートされていなければなりません。

サンプルコード

配列から目的の値を検索するバイナリーサーチのサンプルコードです。

C言語

#include <stdio.h>

#define ARRAY_SIZE 7 /* size of array */

int main(void)
{
    int a[ARRAY_SIZE] = {1,2,3,4,5,6,7}; /* sorted array */
    int left = 0; /* start key of index */
    int right = ARRAY_SIZE; /* end key of index */
    int mid; /* middle key of index */
    int value; /* search value */

    puts("Find value?");
    scanf("%d", &value);

    while(left <= right) {
        mid = (left + right) / 2; /* calc of middle key */
        if (a[mid] == value) {
            puts("Found!\n");
            return 0;
        } else if (a[mid] < value) {
            left = mid + 1; /* adjustment of left(start) key */
        } else {
            right = mid - 1; /* adjustment of right(end) key */
        }
    }
    puts("Not Found.\n");
    return 0;
}