C - 制御の流れ (二分探索(テスト回数と実行速度))

プログラミング言語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.1(文とブロック)、3.2(If-Else)、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()
{
    int x = 1;
    int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = 10;
    int i;
    for (i = 0; i < 1000000000; i++) {
        binsearch(x, v, n);
    }
    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

real 0m26.451s
user 0m26.127s
sys 0m0.023s
$

コード

sample.c

#include <stdio.h>

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

int main()
{
    int x = 1;
    int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = 10;
    int i;
    for (i = 0; i < 1000000000; i++) {
        binsearch(x, v, n);
    }
    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

real 0m27.962s
user 0m27.817s
sys 0m0.018s
$

ループ内で1回だけテストするプログラムの方がループ内で2回テストするプログラムより、sys時間が速くなった。