K&Rを読もう(34) 演習 3-1 バイナリサーチ

GCC

二分探索というやつですね。半分の半分の半分の・・・とやっていく方法。検索以外にも応用が効く。計算処理の高速化とか。バグ探しとか・・・。

演習 3-1

僕の頭が弱いので、再帰で挑戦。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 0x100000

int binsearch(int x, int v[], int low, int high);
int binsearch2(int x, int v[], int low, int high);

int main(void)
{
    int c[MAX];
    int i;
    time_t t;

    for (i = 0; i < MAX; i++)
        c[i] = i;

    t = clock();
    for (i = 0; i < MAX; i++)
        binsearch(i, c, 0, MAX);
    printf("%f\n", difftime(clock(), t));

    t = clock();
    for (i = 0; i < MAX; i++)
        binsearch2(i, c, 0, MAX);
    printf("%f\n", difftime(clock(), t));

    return EXIT_SUCCESS;
}

int binsearch(int x, int v[], int low, int high)
{
    int mid;

    if (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            return binsearch(x, v, low, mid - 1);
        else if (v[mid] < x)
            return binsearch(x, v, mid + 1, high);
        else
            return mid;
    } else {
        return -1;
    }
}

int binsearch2(int x, int v[], int low, int high)
{
    int mid = (low + high) / 2;

    if (low <= high && x != v[mid]) {
        if (x < v[mid])
            return binsearch2(x, v, low, mid - 1);
        else if (v[mid] < x)
            return binsearch2(x, v, mid + 1, high);
    } else {
        if (x == v[mid])
            return mid;
        else
            return -1;
    }
}

久しぶりに長め。

結果は・・・。

640000.000000
710000.000000

改良版はmidの見る位置をちょっとずらしただけ。しかし、if (low <= high && x != v[mid])がウィークポイントになってしまい、改良版の方が遅くなってしまった。早くなる方法もあるのかなぁ・・・。

GDB+再帰はいい感じ。

再帰で書くと、GDBでデバッグがしやすい。

  Breakpoint 1, binsearch (x=0, v=0xbf589090, low=0, high=1048575) at 3.3.c:36
(gdb) step
(gdb) step
..(略  
  Breakpoint 1, binsearch (x=0, v=0xbf589090, low=0, high=524286) at 3.3.c:36
(gdb) step
(gdb) step
..(略  
  Breakpoint 1, binsearch (x=0, v=0xbf589090, low=0, high=262142) at 3.3.c:36
(gdb)

GDBステキ杉。

追記

コーディング勉強日記（仮）: プログラミング言語C 3章演習解答 (前半)のbinserchの方がちょっと早い。

0 〜 0x100000 - 1でテストした所、

640000.000000 K&R
680000.000000 ボクノス
660000.000000 コーディング勉強日記（仮）

となり,K&Rの方が早い。結局の所やってることはみんな一所。