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;
}

プログラム2:プログラム1ではwhileループ文は2回の判断を実行したが、実際には1回だけで十分である(代価はより多くのテストをループの外に置くことである)、この関数を書き換え、ループ内部で1回のテストだけを実行し、2つのバージョンの実行時間を比較する.
これは他人の解法だとは思いませんでしたが、実は2回の判断で、一度にwhileかっこ()に入れて判断しただけです

int binsearch2(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;
    else
        return -1;
}

次はテストを見て、これはやはりとても重要で、後で1つの問題に対して異なる解法の時、テストを行うことができて、どうせ多く他の人のプログラムを勉強します

int main(void) 
{
    int testdata[MAX_ELEMENT];
    int index;                  
    int n = -1;   //                 
    int i;
    clock_t time_taken;
  
    for ( i = 0; i < MAX_ELEMENT; ++i )
        testdata[i] = i;
        
    for ( i = 0, time_taken = clock(); i < 100000; ++i ) 
	{
        index = binsearch(n, testdata, MAX_ELEMENT);
    }
    
    time_taken = clock() - time_taken;

    if ( index < 0 )
        printf("Element %d not found.
", n);
    else
        printf("Element %d found at index %d.
", n, index);
    
    printf("binsearch() took %lu clocks (%lu seconds)
",
           (unsigned long) time_taken,
           (unsigned long) time_taken / CLOCKS_PER_SEC);
    
    for ( i = 0, time_taken = clock(); i < 100000; ++i ) 
	{
        index = binsearch2(n, testdata, MAX_ELEMENT);
    }
    time_taken = clock() - time_taken;
    
    if ( index < 0 )
        printf("Element %d not found.
", n);
    else
        printf("Element %d found at index %d.
", n, index);
        
    printf("binsearch2() took %lu clocks (%lu seconds)
",
           (unsigned long) time_taken,
           (unsigned long) time_taken / CLOCKS_PER_SEC);
    
    return 0;
}

質問:clock()関数とCLOCKS_についてPER_SEC?
答え:clock_t clock(void)はプロトタイプで、実はclock_tは長い整形(long)数である.CLOCKS_についてPER_SEC定数は、1秒に何個のクロックタイミングユニットがあるかを示すもので、LinuxではWindowsと異なる場合があります.
現在の機械演算速度は速く,clock()関数でアルゴリズムの時間効率を記録すると,得られる可能性のある結果は0である.複数回呼び出せばいい