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以下としたが・・）に悩む

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