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

程序二：在程序一中,while循环语句共执行了两次判断，其实只要一次就够了（代价是将更多的测试放在循环体外），重写该函数，使得在循环内部只执行一次测试，比较两个版本运行的时间

解法：我没想出来，这个是别人的解法，其实感觉还是两次判断，只是一次放在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;
}

下面看测试，这个还是很重要的，以后对一个问题不同解法时，可以进行测试下，反正多学习下别人的程序

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", n);
    else
        printf("Element %d found at index %d.\n", n, index);
    
    printf("binsearch() took %lu clocks (%lu seconds)\n",
           (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", n);
    else
        printf("Element %d found at index %d.\n", n, index);
        
    printf("binsearch2() took %lu clocks (%lu seconds)\n",
           (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常量，用来表示一秒钟会有多少个时钟计时单元,在Linux中和Windows可能会不同。

现在的机器运算速度很快，当用clock（）函数记录算法的时间效率，可能得到的结果为0。多次调用就好