应届生笔试编程题

第一题：查找

有一个数组a[n]，数组中的数据是一个无规律的递增数，请写出一个函数用最高效的方式判段关键字num是否在这个数组中。如果存在则返回该数所在数组中的位置，如果不存在则返回0XFFFFFFFF（假定数组长度小于这个值）。

例如：

Int a[]={1,2,3,4,555,666,888,......,444444};

FindNumber(a,sizeof(a)/sizeof(a[0]),3);返回值为2.

解析：

/*斐波那契查找*/  
int F(int i)
{
	if(i<2)
		return i==0? 0:1;
	return F(i-1)+F(i-2);
}
int Fibonacci_Search(int *a,int n,int key)
{
	int low=1,high=n,mid,i,k=0;
	while(n>F(k)-1)             /*计算n位于斐波那契数列的位置*/
		k++;
	for(i=n;i<F(k)-1;i++)       /*将不满的数值补全*/
		a[i]=a[n];

	while(low<=high)
	{
		mid=low+F(k-1)-1;
		if (key<a[mid])
		{
			high=mid-1;
			k=k-1;
		}
		else if (key>a[mid])
		{
			low=mid+1;
			k=k-2;
		}
		else
		{
			if(mid<=n)
				return mid;
			else
				return n;
		}
	}
	return -1;
}
int main(void)
{
	int a[100]={0,1,16,24,35,47,59,62,73,88,99};
	int fibonacci_i=Fibonacci_Search(a,11,59);
	printf("fibonacci_i=%d\n",fibonacci_i);
	return 0;
}

第二题：查找

写一段程序，找出数组中第K大大小的数，输出数所在的位置。例如{2,4