C - 制御の流れ(Else-If、二分探索)

プログラミング言語C 第2版 ANSI規格準拠
B.W. カーニハン D.M. リッチー (著)
石田 晴久 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: C
• Clang (コンパイラ)

プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)の第3章(制御の流れ)、3.3(Else-If)の演習 3-1を解いてみる。

その他参考書籍

• プログラミング言語Cアンサー・ブック 第2版 (クロビス・L．トンド、スコット・E．ギンペル(著)、矢吹 道郎(翻訳))

演習 3-1.

コード

sample.c

#include <stdio.h>

int binsearch(int x, int v[], int n);

int main()
{
    enum last {LENGTH = 1000000};
    int v[LENGTH];
    int i, index;
    
    for (i = 0; i < LENGTH; i++)
        v[i] = i;
    
    index = binsearch(5, v, LENGTH);
    printf("%d\n", index);
    index = binsearch(-10, v, LENGTH);
    printf("%d\n", index);
    
    /* 実行速度の差を確認するため */
    for ( i = 0; i < 10000000; i++) {
        index = binsearch(5, v, LENGTH);
    }
    return 0;
}

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

入出力結果(Terminal)

$ time ./a.out
5
-1

real 0m2.044s
user 0m1.994s
sys 0m0.009s
$

ループの中で二つのテストを行っている場合の実行時間。

コード

sample.c

#include <stdio.h>

int binsearch(int x, int v[], int n);

int main()
{
    enum last {LENGTH = 1000000};
    int v[LENGTH];
    int i, index;
    
    for (i = 0; i < LENGTH; i++)
        v[i] = i;
    
    index = binsearch(5, v, LENGTH);
    printf("%d\n", index);
    index = binsearch(-10, v, LENGTH);
    printf("%d\n", index);
    
    /* 実行速度の差を確認するため */
    for ( i = 0; i < 10000000; i++) {
        index = binsearch(5, v, LENGTH);
    }
    return 0;
}

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

入出力結果(Terminal)

$ time ./a.out
5
-1

real 0m1.813s
user 0m1.799s
sys 0m0.006s
$

1回だけではそんなに差が出なかったから、for loopで何回も検索するようにしてみたものの、そんなに差が出なかった。(というか、while loopの中で2回テストする方が実行速度が速いという結果に。。)