博客

#include<stdio.h>
int Binary_Search(int *a,int n, int key)
{
	int low,high,mid;
	
	low = 0;
	high = n;
	while(low<=high)
	{
		mid = low +(high-low)*(key-a[low])/(a[high] - a[low]);//插值查找
		//mid = (low+high)/2;                                 //折半查找
		if(key<a[mid])
			high = mid - 1;
		else if(key>a[mid])
			low = mid + 1;
		else return mid;
	}
	return 0;
}
int main()
{
	int a[] = {0,1,16,24,35,47,59,62,73,88,99};
	int b = Binary_Search(a,11,62);
	
	printf("key值的位置是:%d",b );
	printf("\n\n");
}

上面是折半查找和插值查找，折半查找的前提条件是需要有序表存储，时间复杂度为O(logn),它显然好于顺序查找的O(n)时间复杂度。但对于频繁执行插入或删除操作的数据来书，不建议使用

/*斐波那契查找*/
int Fibonacci_Search(int *a,int n,int key)
{
	int low,high,mid,i,k;
	
	low=1;
	high=n;
	k=0;
	while(n>F[k]-1)
	{
		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 0;
}