at_yasu's blog

ロード的なことを

二分探索

久しぶりに二分探索のプログラムを書く。本当に久しぶりなので、アルゴリズムでちょっとボケた事してます。


二分探索の説明はWikipediaの項に任せる。

てか、頭回らないため、今回作ったアルゴリズムの説明後回し。普通は探している範囲の最小値と最大値のそれぞれを変数に保持しているんだけど、今回その最大値の部分は、最小値+(配列の要素数/2^(現在の回数))で求めています。ただし、『2^(n-1) < 配列の要素数 < 2^(n)』となるため、『配列の要素数/2^(現在の回数)』が0でかつ余りがある場合に限り検索の処理を実行しています。



下記のファイルがメインプログラムとなります。サンプルの配列数が少なすぎですが (^^;

/* Atsushi Yasui <a.yasui@gmail.com>
 * 2007/05/30 02:56
 */

#include <stdio.h>

const long double double_array[] = {
0.989910828851315L,
1.22177090569497L,
2.20898675072146L,
2.67982212256431L,
3.36758838590818L,
3.94364173582971L,
5.11008451212533L,
5.32642873461018L,
5.6848469502026L,
    5.88373318588388L
};


// Shark Nest loop test.
// 二分探索の再帰ループとwhileループの比較

// Using Double Search.
#define MAX_SIZE (sizeof(double_array)/sizeof(long double))

// debug flag
// #define DEBUG 0
// debug macro
#define dbg(...) \
(printf("%s %u @%s:",__FILE__,__LINE__,__func__), \
 printf(" "__VA_ARGS__))

/* ------------------------------------------------------------------------ */

unsigned int
kai2n (unsigned int n)
{
    return 0x01 << n;
}

/* 再帰ループを使用した方法 */
#define nestLoopSearch(n) _nestLoopSearch((n),  (unsigned int)(MAX_SIZE / kai2n(1)), 1)
unsigned int
_nestLoopSearch (const long double search_value,
                const unsigned int min_ptr_cnt,
                const unsigned int search_count)
{
    unsigned int mySearchCount = search_count;
    unsigned int separate = MAX_SIZE / kai2n(mySearchCount);

    // old value check
    if (separate == 0)
        return min_ptr_cnt;

    mySearchCount++;
    separate = MAX_SIZE / kai2n(mySearchCount);

    // 切り上げの処理
    // 2^(mySearchCount-1) < MAX_SIZE < 2^(mySearchCount) の処理
    if (separate == 0 && MAX_SIZE % kai2n(mySearchCount))
        separate = MAX_SIZE / kai2n(mySearchCount-1);
    
#ifdef DEBUG
    dbg("\n\t\t\tmySearchCount[%u] separate[%u] min_ptr_cnt[%u] double_array[%0.15LF]\n",
        mySearchCount-1,
        separate,
        min_ptr_cnt,
        double_array[min_ptr_cnt]);
#endif // DEBUG

    if (search_value > double_array[min_ptr_cnt]) {
        return _nestLoopSearch(search_value,
                               min_ptr_cnt + separate,
                               mySearchCount);
    }
    else if (search_value < double_array[min_ptr_cnt]) {
        return _nestLoopSearch(search_value,
                               (min_ptr_cnt > separate -1) ? min_ptr_cnt - separate-1 : 0,
                               mySearchCount
                               );
    }
    
    return min_ptr_cnt;
}

/* Whileループを使用した方法 */
unsigned int
whileLoopSearch (const long double search_value)
{
    unsigned int search_cnt = 1;
    unsigned int min_ptr = MAX_SIZE / kai2n(search_cnt);

    while (1) {
        unsigned int separate = MAX_SIZE / kai2n(search_cnt);

        // old value check
        if (separate == 0)
            return min_ptr;
        
        search_cnt++;
        separate = MAX_SIZE / kai2n(search_cnt);
        
        // 切り上げの処理
        // 2^(mySearchCount-1) < MAX_SIZE < 2^(mySearchCount) の処理
        if (separate == 0 && MAX_SIZE % kai2n(search_cnt))
            separate = MAX_SIZE / kai2n(search_cnt -1);

#ifdef DEBUG
        dbg("\n\t\t\tsearch_cnt[%u] separate[%u] min_ptr[%u] double_array[%0.15LF]\n",
            search_cnt,
            separate,
            min_ptr,
            double_array[min_ptr]);
#endif // DEBUG
        
        if (search_value > double_array[min_ptr]) {
            min_ptr += separate;
        }
        else if (search_value < double_array[min_ptr]) {
            min_ptr = (min_ptr > separate-1) ? min_ptr - separate-1 : 0;
        }
        else
            return min_ptr;
    }
}

int main (int argc, const char * argv[]) {

    long double search_array[] = {
        2.60014635032533L,
        0.10984318457492L,
        5.11008451212533L,
        2.40203109108396L
    };
    
    int i = 0;

    for (i = 0; i < (sizeof(search_array)/sizeof(long double)); i++) {
        int num = 0;

        num = nestLoopSearch(search_array[i]);
        printf("%0.15LF -> double_array[%u] = %0.15LF\n",
               search_array[i], num, double_array[num]);
    }

    for (i = 0; i < (sizeof(search_array)/sizeof(long double)); i++) {
        int num = 0;

        num = whileLoopSearch(search_array[i]);        
        printf("%0.15LF -> double_array[%u] = %0.15LF\n",
               search_array[i], num, double_array[num]);
    }

    return 0;
}