« 2009年3月 | トップページ | 2009年7月 »

2009年5月の1件の記事

2009年5月 4日 (月)

Googleブック検索と二分探索

あまり話題になっていないようなGoogleブック検索ですが、そこで「ビューティフルコード」を立ち読みして、あー二分検索くらい実装できないとなー、と思って、ためしに書いてみました。一応説明すると、二分探索ってのは、ソートされた配列から、ある値の位置を探索する手法のことで、配列の真ん中、さらに半分の真ん中、さらに半分の真ん中・・・って言う風に二分割しながら「見つかる」まで探すやりかた。

/* 二分探索処理関数
 * key : 探索する値
 * sizeofarray: 探索する配列の長さ
 * p_array :探索する配列(の先頭要素)へのポインタ
 * 返り値: keyがある配列のindex(0 ... sizeofarray - 1)か、見つからない場合は-1
 * */
int search(int key, int sizeofarray, int *p_array){
    /* 探索範囲の左端のindex。最初は全探索範囲の一番左。随時変わる */
    int left_index = 0;        /* 探索範囲の右端のindex。最初は全探索範囲の一番右。随時変わる */
    int right_index = sizeofarray - 1;

    /* 探索範囲の要素数。随時変わる */
    int length = 0;        /* 探索範囲の「まん中」のindex。随時変わる */
    int target_index = 0;

    /* 探索範囲が偶数(0)か、奇数(1)か*/
    int mod = 0;

    while(1){                /* 探索範囲の要素数とまん中のindexを求める */
        /* 要素数が偶数の場合は、右側になることに注意 */
        length       = right_index - left_index + 1;
        target_index = left_index  + length / 2;
        mod = length % 2;

        /* まん中の値がkeyに一致するかのチェック  */
        if ( p_array[target_index] == key ) {
            /* 発見! */
            return target_index;
        }
        else if ( length <= 1)
        {
            /* 探索対象が1つ(以下)なのに、keyに一致しないということは、
             * 結局「無い」ということ */
            return -1;
        }
        else if ( key < p_array[target_index] ){
            /* targetの前にあるかも */
            /* 新しい探索範囲で探索 */
            left_index  = target_index - length / 2;
            right_index = target_index - 1;
        }
        else {
            /* targetの後ろにあるかも */
            /* 新しい探索範囲で探索 */
            left_index  = target_index + 1;
            right_index = target_index + length / 2 - 1 + mod;
        }
    }
    /* ここにはこない */
    return -2;
}

最初は再起呼び出しでやってみてたんだけど、必要も無いのに再起呼び出しするのもあれだなー(スタック積みあがっちゃうし)と思って修正。実装で考えたポイントとしては・・・

  • 探索範囲を左端(left_index)と右端(right_index)で定義して、それをどんどん縮めていく
  • 探索範囲の幅を意識する必要がある(length / 2)
  • length が偶数か奇数かによって、次の探索範囲が微妙に変わるので、その調整が必要
  • 探索の否定的な終了(ここには無いよ!)の適切な条件設定(lengthが1以下としたが・・)に悩む

ってところ。バグ、改善ポイントなどご指摘大歓迎。

| | コメント (2) | トラックバック (0)

« 2009年3月 | トップページ | 2009年7月 »