バイナリサーチ

バイナリサーチ（二分探索）とは

ソート済みの配列データで指定されたデータ（の位置）を探す。同一の値はないものする。 まず、中央の値を見て、探すものと一致すればそれで終わり。 そうでなければ、値を比べてみて、配列の前の方にあるか、後ろの方にあるかを判断する。 どちらか配列半分で同じことを繰り返す。

例えば、サイズ1000の配列から探す場合、探す配列の範囲は 1000、500、250、… と半減していく、 最悪10回で見つかる。

C言語の実装例[1]

int binary_search(int ary[], int key, int imin, int imax) {
    if (imax < imin) {
        return KEY_NOT_FOUND;
    } else {
        int imid = imin + (imax - imin) / 2;
        if (ary[imid] > key) {
            return binary_search(ary, key, imin, imid - 1);
        } else if (ary[imid] < key) {
            return binary_search(ary, key, imid + 1, imax);
        } else {
            return imid;
        }
    }
}

Java/Android Java の Arrays.binarySearch

  binarySearch(int[] a, int key)
  binarySearch(long[] a, int key)

参考記事